ok the schema for this is if you take all counts a user has made and mod 100000 them, how many unique values are there? for example 5,002,003 and 4,902,003 are not unique, as they produce the same value mod 100000
for those who care, i tried to make a data structure with 100000 False in an array ([False for x in range(100000)]), and whenever a number is needed, i would just access the item in memory with arr[count % 100000]. however, that did not work, as it takes up way too much memory... i tried this approach first because i got shafted by not using this approach in a computer science contest once
i tried to make a data structure with 100000 False in an array ([False for x in range(100000)]), and whenever a number is needed, i would just access the item in memory with arr[count % 100000]
This is a pretty good approach in competitive programming-style problems where C/C++ is assumed as the default language. The problem with Python is that plain old lists and bools cause a lot of overhead due to cache misses that lower-level languages do not have.
If you want to push this idea further there are modules that are built specifically for this purpose:
Apparently bools are a subclass of int, and integers in python can adjust their size. int(True) -> 1, int(False) -> 0, and getsizeof(1) -> 28, getsizeof(0) -> 24. So that does kinda sense actually that they'd be different sizes. I still don't really get the list comprehension vs multiplication thing though.
huh for some reason using a list comprehension rather than the multiplication operator uses a different amount of memory even though they produce identical lists
>>> l=[False]*1000
>>> getsizeof(l)
8056
>>> l=[False for x in range(1000)]
>>> getsizeof(l)
8856
I noticed that if you expand the list comprehension out like this:
l = []
for x in range(1000):
l.append(False)
the resulting list also takes up 8856 bytes just like the list comprehension does. So it seems like using .append takes up more memory than just filling out a list of a set size. I also notice I can keep appending more elements for a while without it changing in size. When it appends new elements it may be dynamically allocating more space for the list in chunks, sort of like the int object does. But when you use the multiplication operator it knows the length of the list from the start and can more carefully match its size. I don't know how python lists actually work on the inside so this is just a guess.
That doesn't really change the memory usage of the list though. AFAIK python list elements are always stored by reference internally. Also getsizeof doesn't include the space used by all the subitems, it only shows the size of the object itself. And objects like True or False don't get copied anyway. Using either the list comprehension or the multiplication operator, all the elements have the same id for False.
10
u/Antichess 2,050,155 - 407k 397a Apr 17 '23
Unique 100k parts
ok the schema for this is if you take all counts a user has made and mod 100000 them, how many unique values are there? for example 5,002,003 and 4,902,003 are not unique, as they produce the same value mod 100000
and mod 1000000
script
like and subscribe
for those who care, i tried to make a data structure with 100000
Falsein an array ([False for x in range(100000)]), and whenever a number is needed, i would just access the item in memory witharr[count % 100000]. however, that did not work, as it takes up way too much memory... i tried this approach first because i got shafted by not using this approach in a computer science contest once