Timeline for Sieve31, my sieve of Eratosthenes returning IEnumerable<int>
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 9, 2015 at 21:05 | comment | added | Rick Davin | No, but very nice link. I base my info on fact I get actual out of memory exception if I try to dump ToList or if I tried using a bool[] with the Sieve32 (the uint equivalent of Sieve31). | |
| Sep 9, 2015 at 20:00 | comment | added | Der Kommissar | @RickDavin Have you looked into anything from this question on SO? | |
| Sep 1, 2015 at 15:54 | comment | added | Rick Davin | FOLLOW UP: I applied and tested this answer more. Time was reduced from 38.8 seconds to 22.2 seconds yielding 43% faster performance. Memory footprint increased six-fold going from 143 MB to 1 GB. However ... I lost the feature of using .ToList() with an upperLimit of int.MaxValue as it now throws an out of memory exception. | |
| Aug 29, 2015 at 23:15 | comment | added | Der Kommissar | @RickDavin Aha, that makes sense. I'll not bother trying it then. :) Glad this was helpful to you, as well. | |
| Aug 29, 2015 at 23:15 | comment | added | Rick Davin | No need. What you have just described is what BitArray already does. See BitArray Reference Source at referencesource.microsoft.com/#mscorlib/system/collections/… | |
| Aug 29, 2015 at 23:10 | comment | added | Der Kommissar | @RickDavin That's very curious - you could potentially make an int[] of int[(ToIndex(UpperLimit) + 1) / 8] and use some "cute" math to get the values/etc you need. I might try an experimentation involving just that when I am back home - I'm on vacation right now so it won't happen until at least Monday, if you are interested in the result. :) | |
| Aug 29, 2015 at 23:02 | comment | added | Rick Davin | This answer works fine for Sieve31 but would produce an out of memory exception for Sieve32, where one must still use BitArray. But since this question is about Sieve31, I have marked your answer as the accepted answer. | |
| Aug 29, 2015 at 22:47 | comment | added | Rick Davin | Sorry for late response. Been out of town. Very nice answer. For past 18 months of reading CR I have believed that BitArray is the "best" route. It is still the smallest memory route but certainly not the fastest. You are right about speed boost, but it does come at price of using 6x memory. I discovered that internally a BitArray actually uses a int[] as its backing field so that means a lot of internal bit twiddling is done to make it appears as a stream of bits. | |
| Aug 29, 2015 at 22:44 | vote | accept | Rick Davin | ||
| Aug 27, 2015 at 19:57 | comment | added | t3chb0t | It can be faster. See my answer to your answer :-) | |
| Aug 26, 2015 at 20:25 | history | edited | Der Kommissar | CC BY-SA 3.0 | added 75 characters in body |
| Aug 26, 2015 at 20:18 | history | answered | Der Kommissar | CC BY-SA 3.0 |