Re: Comparing sequences with range objects
Op 9/04/2022 om 02:01 schreef duncan smith: On 08/04/2022 22:08, Antoon Pardon wrote: Well my first thought is that a bitset makes it less obvious to calulate the size of the set or to iterate over its elements. But it is an idea worth exploring. def popcount(n): """ Returns the number of set bits in n """ cnt = 0 while n: n &= n - 1 cnt += 1 return cnt and not tested, def iterinds(n): """ Returns a generator of the indices of the set bits of n """ i = 0 while n: if n & 1: yield i n = n >> 1 i += 1 Sure but these seem rather naive implementation with a time complexity of O(n) where n is the maximum number of possible elements. Using these would turn my O(n) algorithm in a O(n^2) algorithm. -- Antoon Pardon. -- https://mail.python.org/mailman/listinfo/python-list
Re: What to do to correct the error written below:
On Sat, 9 Apr 2022 04:59:05 -0700 (PDT), NArshad wrote: > I have accidentally deleted one account in a Django project because of > which one of the pages is no more accessible and is giving the error > written below: > > IndexError at /view_issued_book/ > list index out of range > > and the error is in the line: > > t=(students[i].user,students[i].user_id,books[i].name,books[i].isbn,issuedBooks[0].issued_date,issuedBooks[0].expiry_date,fine) > [snip] Without seeing more of the code, one can only guess, but it appears that the data being processed reside in arrays named "students" and "books", which are indexed by an integer i. The "list index out of range" error probably results from i being too large -- running off the end of the array, perhaps because of the deleted account. You could confirm this by printing i, len(students), and len(books) just before the failing line. -- To email me, substitute nowhere->runbox, invalid->com. -- https://mail.python.org/mailman/listinfo/python-list
Re: Comparing sequences with range objects
On 10/04/2022 21:20, Antoon Pardon wrote: Op 9/04/2022 om 02:01 schreef duncan smith: On 08/04/2022 22:08, Antoon Pardon wrote: Well my first thought is that a bitset makes it less obvious to calulate the size of the set or to iterate over its elements. But it is an idea worth exploring. def popcount(n): """ Returns the number of set bits in n """ cnt = 0 while n: n &= n - 1 cnt += 1 return cnt and not tested, def iterinds(n): """ Returns a generator of the indices of the set bits of n """ i = 0 while n: if n & 1: yield i n = n >> 1 i += 1 Sure but these seem rather naive implementation with a time complexity of O(n) where n is the maximum number of possible elements. Using these would turn my O(n) algorithm in a O(n^2) algorithm. I thought your main concern was memory. Of course, dependent on various factors, you might be able to do much better than the above. But I don't know what your O(n) algorithm is, how using a bitset would make it O(n^2), or if the O(n^2) algorithm would actually be slower for typical n. The overall thing sounds broadly like some of the blocking and clustering methods I've come across in record linkage. Duncan -- https://mail.python.org/mailman/listinfo/python-list
Re: Comparing sequences with range objects
It sounds a little like you're looking for interval arithmetic. Maybe https://pypi.org/project/python-intervals/1.5.3/ ? On Thu, Apr 7, 2022 at 4:19 AM Antoon Pardon wrote: > I am working with a list of data from which I have to weed out duplicates. > At the moment I keep for each entry a container with the other entries > that are still possible duplicates. > > The problem is sometimes that is all the rest. I thought to use a range > object for these cases. Unfortunatly I sometimes want to sort things > and a range object is not comparable with a list or a tuple. > > So I have a list of items where each item is itself a list or range object. > I of course could sort this by using list as a key function but that > would defeat the purpose of using range objects for these cases. > > So what would be a relatively easy way to get the same result without > wasting > too much memory on entries that haven't any weeding done on them. > > -- > Antoon Pardon. > -- > https://mail.python.org/mailman/listinfo/python-list > -- https://mail.python.org/mailman/listinfo/python-list
Re: Comparing sequences with range objects
On 2022-04-10 at 22:20:33 +0200, Antoon Pardon wrote: > > > Op 9/04/2022 om 02:01 schreef duncan smith: > > On 08/04/2022 22:08, Antoon Pardon wrote: > > > > > > Well my first thought is that a bitset makes it less obvious to calulate > > > the size of the set or to iterate over its elements. But it is an idea > > > worth exploring. > > > > > > > > > > > def popcount(n): > > """ > > Returns the number of set bits in n > > """ > > cnt = 0 > > while n: > > n &= n - 1 > > cnt += 1 > > return cnt > > > > and not tested, > > > > def iterinds(n): > > """ > > Returns a generator of the indices of the set bits of n > > """ > > i = 0 > > while n: > > if n & 1: > > yield i > > n = n >> 1 > > i += 1 > > > Sure but these seem rather naive implementation with a time complexity of > O(n) where n is the maximum number of possible elements. Using these would > turn my O(n) algorithm in a O(n^2) algorithm. O(n) where n is the expected number of elements. The loops iterate once for each bit actually contained in the set, which is usually [much] less than the size of the universe. If you have lots and lots of elements in your sets, or your universe is large and n is a long integer, then these may not be as efficient as other methods. You know your data better than we do. -- https://mail.python.org/mailman/listinfo/python-list
Re: Comparing sequences with range objects
Two more things: 1) There are also modules that do interval arithmetic with reals, not just integers. EG: https://pyinterval.readthedocs.io/en/latest/ 2) If you don't mind a small amount of inaccuracy you can often get things down to less than one bit per element for presence/absence, using a bloom filter. EG: https://pypi.org/project/drs-bloom-filter/ On Sun, Apr 10, 2022 at 5:31 PM Dan Stromberg wrote: > > It sounds a little like you're looking for interval arithmetic. > > Maybe https://pypi.org/project/python-intervals/1.5.3/ ? > > On Thu, Apr 7, 2022 at 4:19 AM Antoon Pardon wrote: > >> I am working with a list of data from which I have to weed out duplicates. >> At the moment I keep for each entry a container with the other entries >> that are still possible duplicates. >> >> The problem is sometimes that is all the rest. I thought to use a range >> object for these cases. Unfortunatly I sometimes want to sort things >> and a range object is not comparable with a list or a tuple. >> >> So I have a list of items where each item is itself a list or range >> object. >> I of course could sort this by using list as a key function but that >> would defeat the purpose of using range objects for these cases. >> >> So what would be a relatively easy way to get the same result without >> wasting >> too much memory on entries that haven't any weeding done on them. >> >> -- >> Antoon Pardon. >> -- >> https://mail.python.org/mailman/listinfo/python-list >> > -- https://mail.python.org/mailman/listinfo/python-list
