3 ms·
I have my own O(n^2) blow-up story. Back in the day I wrote some Google AdWords analysis software in a functional language. Being written in a functional lang
by rwmj 7y ago
I have my own O(n^2) blow-up story. Back in the day I wrote some Google AdWords analysis software in a functional language. Being written in a functional language meant that using association lists (linked lists for key/value) was very natural. Anyway these were only used to load the analysis inputs which was written in an Excel spreadsheet (the customer insisted on this!), exported to a CSV and loaded into the software. The spreadsheet was only perhaps 5 rows so, whatever.
One day I got a call from the customer that his analysis was taking 6 hours to run, for a program that should have finished in a fraction of a second. It turned out the customer had tried to load a 30,000 row spreadsheet of input. The program would on every loop iterate over the input association list, resulting in classic O(n^2) performance overall.
After changing all the places to use a hash table it again ran in sub-second, although the code was nowhere near as elegant.
- masklinn 7y agoWhy would the code be "nowhere near as elegant"? Lack of a functional / persistent map? Because I'd expect all maps to provide roughly similar interfaces whether they're assoc lists, hashmaps, btrees, HAMT, …: iterate all entries, presence of a key, get value for key, insert (key, value), remove key (and value), possibly some other niceties on top (e.g. update value in-place, merge maps, …) but those are extras.
- marcosdumay 7y agoOn my experience, moving away from a list of pairs add a parsing stage that one may be able to omit otherwise.
- masklinn 7y agoI don't understand how or why. What's the "parsing stage"? You have an associative array, a key, a value, and a function to associate the k, v pair to the array. You're moving from let m' = (k, v) : m to let m' = insert k v m What there would make the code "nowhere near as elegant"?
- rcthompson 7y agoIt's a function of the language. If you're working a Lisp, association lists are very much the "default" for mappings, and the style of code built around them is very clear as a result (in most lisp-like languages, at least). For example, there's no special constructor for an alist: you just create a list, which can be done using the lisp syntax itself. Whereas for something like a hash table, you likely have to call a constructor or something. It's all just a consequence of lisp's syntax and structure being largely built around list manipulation. In contrast, languages like Perl or Python have literals and syntax support for both lists and mapping-type data structures (hashes in Perl, dicts in Python), so using either one is roughly equally elegant, and you are more free to choose one or the other based on performance concerns.
- marcosdumay 7y agoI don't get the downvoting for not understanding. But well. In Haskell assotiation lists are also the default, as they don't impose any stictness and are very fast to iterate. So that is what you get from libraries. If you need a map, you will have to first construct it, then run your code. But of course, if you are the one creating the lists, it does change very little.
- cogman10 7y agoThe one benefit of n^2 is it is really easy to do without any additional memory or data structure requirements. To make an n^2 algorithm n (or n log n), you pretty much always need to add in some constant time or logarithmic data structure. That requires tracking that structure, usually generating a good key, etc. I'm not saying that's really all that extreme. It just means your previous 5 line algorithm will often "bloat" to 10 or more lines with a new concept to track. This is where I see some saying "not elegant".
- masklinn 7y agoThat still makes no sense. The GP is literally just talking about switching from an association list to a hashmap: > Being written in a functional language meant that using association lists (linked lists for key/value) was very natural. […] After changing all the places to use a hash table it again ran in sub-second, although the code was nowhere near as elegant. You're not tracking more things (just tracking a hashmap instead of a list), you're not generating anything different, you don't have any new concept to track. All I'm asking is where the apparently significant loss of elegance would come from.
- monoideism 7y ago> apparently significant loss of elegance would come from. In a word, you're losing a persistent data structure[1]. And this can go beyond just loss of elegance. Sometimes, functional programs will depend on immutability of data structures for performance optimizations and even for functionality (like keeping a version history). 1. https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure
- jimbo1qaz 7y agoWhen was this story from? From my limited knowledge, I think persistent hashmaps have been available since Clojure 1.0 (2009) or before? (hash-map, https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/hash-map https://clojure.github.io/clojure/clojure.core-api.html#cloj...).
- rwmj 7y agoTo answer this I had to remember how to use CVS again because the code was from 2004 ... It turns out that (for reasons I don't recall now) I modified the code to limit what could appear in the spreadsheet and use an alternate algorithm only when there were more than 500 lines in the spreadsheet. The final code was below. Unfortunately I lost the actual change, but you can work it out: let max_map_regexp = 500 (* lines - see below *) (* Format of the map_file. *) type map_file_t = | Map of ((Pcre.regexp * Pcre.regexp * Pcre.regexp * Pcre.regexp) * (float option * bool * Inp.params)) list | Hash of (string * string * string * string, float option * bool * Inp.params) Hashtbl.t let run map_filename = (* Parse the map file. *) let csv = Csv.load map_filename in if Csv.lines csv < 2 then failwith (map_filename ^ ": bid file should contain headings and at least one row of data"); let csv' = List.tl csv in (* Ignore headings. *) ... (* If the map file is > max_map_regexp lines long then regular * expressions are banned and a more efficient hash table format * is used for lookups. Otherwise the program takes far too long * to run. *) let map_file = if List.length map_file <= max_map_regexp then ( Map (List.map ( fun ((c_name, ag_name, kw_text, kw_type), a) -> (compile c_name, compile ag_name, compile kw_text, compile kw_type), a ) map_file) ) else ( (* Regexps banned from large map files. *) Hash ( let h = Hashtbl.create (List.length map_file) in List.iter ( fun ((c_name, ag_name, kw_text, kw_type), a) -> Hashtbl.add h (c_name, ag_name, kw_text, String.lowercase kw_type) a ) map_file; h ) ) in