This reminds me I once wrote a hyper-exponential graph processing algorithm, in the range of O(2^2^n), and I still believe it was the right choice because: 1) It was much easier to understand than a faster alternative, and 2) I could mathematically guarantee that the largest value of n was something like 8 or 9, so you could argue that it was in fact a constant time operation.
2^2^9 is 1.340781e+154
O(n^2), again, now in Windows Management Instrumentation
111–120 of 232 posts
Re: O(n^2), again, now in Windows Management Instrumentation
#112Ah, this brings back the memory of my O(n^2) fiasco. I wrote a low level file system storage driver in the past. In the caching layer, there's a need to sort by LRU time for cache eviction. It's a minor thing not run often and I wanted to move quickly. Also since it's low level kernel mode code, I wanted the code to be simple and correct. The number of cache entries was not big. Bubble sort was adequate for small N,…
Re: O(n^2), again, now in Windows Management Instrumentation
#113This reminds me I once wrote a hyper-exponential graph processing algorithm, in the range of O(2^2^n), and I still believe it was the right choice because: 1) It was much easier to understand than a faster alternative, and 2) I could mathematically guarantee that the largest value of n was something like 8 or 9, so you could argue that it was in fact a constant time operation.
Could you explain more? As the other commenter pointed out, 2^2^9 = 2^512 which is an astronomically large number (far more than the number of atoms of ordinary matter in the observable universe). Something doesn't seem right.
Re: O(n^2), again, now in Windows Management Instrumentation
#114Ah, this brings back the memory of my O(n^2) fiasco. I wrote a low level file system storage driver in the past. In the caching layer, there's a need to sort by LRU time for cache eviction. It's a minor thing not run often and I wanted to move quickly. Also since it's low level kernel mode code, I wanted the code to be simple and correct. The number of cache entries was not big. Bubble sort was adequate for small N,…
I had a slow week babysitting something else so I just let it chew away in the background, while doing other things like documentation and requirements work, noting down the time, adding one more module and running it again. The last one I was willing to do took 18 hours to load. It was still running when I got back to the office the following day.
To this day, I can't recall ever seeing any production performance bug with greater than n cubed complexity. This bug progressed at n to the fifth. Truly, a thing of singular beauty.
Thankfully they had a workaround that dropped it to something like n^2 (30 minutes became less than 5) and a bug fix not too long after.
Re: O(n^2), again, now in Windows Management Instrumentation
#115Re: O(n^2), again, now in Windows Management Instrumentation
#116Earlier quoted context omitted.
This is absolutely the better analysis. Many times, especially in agile-world, you get away with things as fast and as reasonable as you can. And that usually means O(n) as it is perfectly acceptable for a single call... But when an O(n) calls another O(n) is where you run into trouble. But at the beginning, nobody was planning for that call to be fast - implicit requirements lead it that way. In some ways, being abl…
> Identification of critical API calls and respective timings would be integral to continue building the GUI elements. But we all know how waterfall is poo-pooed these days. If you've worked out which API calls are happening and how often, you've already written most of the application. It's just that it might be on paper or in pseudocode. Waterfall was abandoned because getting to that level of detail takes far too…
My suggestion of building a first test version to, amongst other things, at least get our feets wet with the programming language (which most of us had hardly any experience with), then throw it completely away and restart "from scratch" (but with a better idea as of what we were supposed to do) was rejected.
Re: O(n^2), again, now in Windows Management Instrumentation
#117Batch scripts themselves are O(n^2) because the shell closes and reopens them after each line (even comments or even blank lines), and the scan to get to line `n` takes O(n) time and disk bandwidth.
That is just plain incorrect, local variables would not work in scripts if that were the case.
I recall that some people would put GOTO statements to jump across large comment blocks in the days where reading a few KB was noticeable.
Re: O(n^2), again, now in Windows Management Instrumentation
#118Earlier quoted context omitted.
That presupposes that you can start with a big pile of bad APIs and somehow incrementally approach something worth having. That's not consistent with my experience. In my experience the innermost APIs, the ones that get written down first, are effectively cast in stone and dictate the quality of the whole product, forever. The first draft of a system is the one that should have all its APIs worked out with a pencil b…
You are right. It is typically more effective to write one implementation as a hacky prototype, play with it a bit, throw it away, and then rewrite a production implementation from scratch, so that the mistakes of a design made by someone inexperienced don’t get baked in forever. Unfortunately there are cultural/psychological factors which often preclude or discourage this method, even if it would save time and produ…
Re: O(n^2), again, now in Windows Management Instrumentation
#119I 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 softw…
Why 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.
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
... (* 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
(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
)
) inRe: O(n^2), again, now in Windows Management Instrumentation
#120Earlier quoted context omitted.
That is just plain incorrect, local variables would not work in scripts if that were the case.
I definitely remember both reading about and experiencing this years ago, but I can't seem to find a source and it's driving me crazy (will search more later). I imagine variables would persist in the shell's memory. I'm talking about an implementation detail of the batch shell script parser/runner. I recall that some people would put GOTO statements to jump across large comment blocks in the days where reading a few…