Opened 6 years ago

Closed 6 years ago

#19492 closed enhancement (fixed)

Optimize linear codes: __eq__, dual_code and commented debug lines

Reported by: dlucas Owned by:
Priority: major Milestone: sage-7.0
Component: coding theory Keywords:
Cc: Merged in:
Authors: David Lucas Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: b869837 (Commits, GitHub, GitLab) Commit: b869837b6732e6c0d9458e18c48abb4957e63387
Dependencies: Stopgaps:

Status badges

Description

Some code in LinearCode.py is quite old and/or slow, and could be optimized. This tickets proposes a faster implementation for __eq__ and dual_code methods. It also removes a lot of commented debug lines.

Change History (12)

comment:1 Changed 6 years ago by dlucas

  • Branch set to u/dlucas/clean_linear_code

comment:2 Changed 6 years ago by dlucas

  • Authors set to David Lucas
  • Commit set to d64c3603f5f870f4d35cfd85ce74c01c5fd6a4f9
  • Status changed from new to needs_review

Let C be a linear code with H a parity check matrix of C. The generator matrix of C's dual is H. I made changes in AbstractLinearCode's dual_code method to use that property instead of the old implementation and got something faster.

I also rewrote AbstractLinearCode's __eq__ which is now less heavy and a bit faster.

Finally, I removed a lot of old debug prints that were still present in this file as commented lines.

This is now ready for review.


New commits:

eba939bChanges in dual_code method
d64c360Changes in __eq__ method, removed commented debug lines

comment:3 Changed 6 years ago by jdemeyer

  • Summary changed from Cleaning linear codes: __eq__, dual_code and commented debug lines to Optimize linear codes: __eq__, dual_code and commented debug lines

comment:4 Changed 6 years ago by vdelecroix

  • Milestone changed from sage-6.10 to sage-7.0
  • Status changed from needs_review to needs_work

The following would be cleaner on two lines.

+        Ks, rbas = self.parity_check_matrix().right_kernel(), right.gens()

Otherwise it looks good.

comment:5 Changed 6 years ago by git

  • Commit changed from d64c3603f5f870f4d35cfd85ce74c01c5fd6a4f9 to f3a7f0790113ce41b9822ea7722796afbaa8342d

Branch pushed to git repo; I updated commit sha1. New commits:

f3a7f07Integrated reviewer's comment

comment:6 Changed 6 years ago by dlucas

  • Status changed from needs_work to needs_review

Thanks for your input.

I changed the code to what you suggested. I also fixed a silly copy-paste mistake two lines below the one you mentioned.

David

comment:7 Changed 6 years ago by vdelecroix

While you are at it, the print statements like

print " t = ",t," , v = ",n," , k = ",w," , lambda = ",wts[w]*binomial(w,t)/binomial(n,t)

are really ugly. Could you do something cleaner like

print "t={} v={} k={} lambda={}".format(t, n, w, wts[w]*binomial(w,t)/binomial(n,t))

comment:8 Changed 6 years ago by jdemeyer

Even better would be

print("t={} v={} k={} lambda={}".format(t, n, w, wts[w]*binomial(w,t)/binomial(n,t)))

since that's compatible with Python 2 and 3.

comment:9 Changed 6 years ago by git

  • Commit changed from f3a7f0790113ce41b9822ea7722796afbaa8342d to b869837b6732e6c0d9458e18c48abb4957e63387

Branch pushed to git repo; I updated commit sha1. New commits:

b869837Changed some print statements to something cleaner

comment:10 Changed 6 years ago by dlucas

It's done. I picked Jeroen's suggestion for the new statements.

comment:11 Changed 6 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

comment:12 Changed 6 years ago by vbraun

  • Branch changed from u/dlucas/clean_linear_code to b869837b6732e6c0d9458e18c48abb4957e63387
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.