Timeline for Why is FreeQ so much faster for some specific variable names?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 21, 2019 at 0:35 | vote | accept | Ray Shadow | ||
| Apr 30, 2019 at 18:18 | answer | added | Ray Shadow | timeline score: 17 | |
| Apr 29, 2019 at 10:02 | comment | added | SonerAlbayrak | @Shadowray Of course, my bad! Thank you for pointing it out :) | |
| Apr 29, 2019 at 9:54 | comment | added | Ray Shadow |
@Soner There is a difference in your timings, because RandomChoice takes time to create the expression. In the first expression you include RandomChoice inside Timing, but in the second you don't. This is not related to FreeQ performance.
|
|
| Apr 29, 2019 at 9:24 | comment | added | SonerAlbayrak |
@DanielLichtblau's point can also be seen if we compare RepeatedTiming[FreeQ[RandomChoice[{a, c}, 1000000], b]] with With[{listac = RandomChoice[{a, c}, 1000000]},RepeatedTiming[FreeQ[listac, b]]] . Clearly, the standard $O(n)$ complexity reduces to $O(1)$ due to the way the variable listac is internally stored.
|
|
| Apr 26, 2019 at 21:47 | comment | added | Daniel Lichtblau | See tutorial/SomeNotesOnInternalImplementation. "Each expression contains a special form of hash code that is used both in pattern matching and evaluation." So in some cases what would be an O(n) test is instead O(1). | |
| Apr 26, 2019 at 17:10 | history | edited | Ray Shadow | CC BY-SA 4.0 |
fixed typo
|
| Apr 26, 2019 at 3:36 | comment | added | march |
This is bizarre. I tried this same thing with all the different (lower-case) letters of the alphabet in the second spot. All of the RepeatedTimings were really fast, except for t, u, and v!
|
|
| Apr 25, 2019 at 22:37 | history | edited | Ray Shadow | CC BY-SA 4.0 |
improved formulation and examples
|
| Apr 25, 2019 at 21:00 | history | tweeted | twitter.com/StackMma/status/1121519388794994688 | ||
| Apr 25, 2019 at 19:14 | comment | added | ktm | My guess is that it has something to do with some sort of hash table data structure, but I'm not sure in what capacity. | |
| Apr 25, 2019 at 19:08 | history | edited | Ray Shadow | CC BY-SA 4.0 |
added tag
|
| Apr 25, 2019 at 18:33 | history | asked | Ray Shadow | CC BY-SA 4.0 |