Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

It Can Happen to You

mattkeeter.com

Post reply on HN
Print view View original

201–210 of 419 posts

Re: It Can Happen to You

#201

Post by TeMPOraL »

thaumasiotes wrote: post #184
alexchamberlain wrote: post #166

Earlier quoted context omitted.

It makes me chuckle when hash maps are stated to be O(1) insertions. Which is true, in respect to the number of items in the map, assuming the map doesn't need resizing and there isn't a hash collision... but it's generally not true in respect to the key length. (I think most implementations are O(ln), where l is the length of the key and n is the number of inserted items, assuming the hash function is O(l) - the _am…

> assuming the map doesn't need resizing This isn't a big difficulty; it's still amortized O(1). > and there isn't a hash collision This is a real difficulty, unless you allow map resizing. Luckily, we do. > but it's generally not true in respect to the key length. OK, but in most cases the key length is constant, making anything that depends on the key length O(1) by definition.

I'm guessing GP means the complexity guarantee sidesteps the complexity of the hashing function. It probably doesn't matter all that much in typical case - I'm guessing 80-90% of hash map use is with very short strings.

Re: It Can Happen to You

#202

Post by beached_whale »

tux3 wrote: post #15

The moral of the story, as far as I'm concerned: do NOT parse strings in C! Use a library, prefferably in a higher-level language. C string handling is a mess of viciously surprising APIs, juggling those particular footguns is almost certainly not your least bad option.

My biggest issue with c-strings is that by requiring a zero terminator and a single char const , it forces a lot of copies(when truncating) and calls to strlen(caller doesn't know the length).

Had it been a char const /size_t or a pair of char const * for first/last it should be both safer and faster. I prefer the later as a pair of pointers doesn't require updating both when iterating with the first ptr.

Re: It Can Happen to You

#203

Post by SuchAnonMuchWow »

virgilp wrote: post #173
lostcolony wrote: post #146

Earlier quoted context omitted.

Fair point; I'm confusing my terminology. Analogy and realization still holds.

Also, already sorted data.. in reverse order. If it's already sorted in the right order, quicksort takes linear time. This is an important difference - data you use might indeed often be appropriately sorted, but in practice will seldom be sorted in reverse order.

If it's already sorted in the right order, quicksort runs in O(n log n). quicksort is O(n log n) bestcase, O(n*n) worstcase.

Re: It Can Happen to You

#204

Post by kibibyte »

smallnamespace wrote: post #179
Jyaif wrote: post #147

Earlier quoted context omitted.

Can you point me towards some source code where a human can't find the algorithmic complexity?

Humans can't tell you whether this program will run forever on any particular (positive integer) input, or whether all inputs terminate. def collatz(n): while n != 1: print(n) if n % 2 == 0: n = n // 2 else: n = n * 3 + 1 print(1)

I think your indentation needs to be adjusted? Like so:

  def collatz(n):
      while n != 1:
          print(n)
          if n % 2 == 0:
              n = n // 2 
          else:
              n = n * 3 + 1

      print(1)
Otherwise, n = 1 terminates, and n != 1 gets stuck looping at lines 2-3.

Re: It Can Happen to You

#205

Post by zbendefy »

chihuahua wrote: post #88
decasia wrote: post #14

Earlier quoted context omitted.

Yes, I absolutely think profiling and then only optimizing the actual problems is always a sound choice. I don't check the docs for every library function I use. I'm just saying, it wouldn't hurt if, when you do read the docs for standard library functions, the algorithmic complexity was mentioned in passing.

In principle, that sounds good. But then it can happen that you profiled when N=1000 and it seems fine. Then a few years later (like in GTA), N has grown to 63,000 and it's no longer fine. It seems unlikely the developer will go back and profile it again. Also, I think the original Windows Update algorithm for figuring out which updates you needed to download started out fine, but 20 years later it turns out it's qua…

also dont forget the quadratic time desktop icon arrangement: https://news.ycombinator.com/item?id=26152335

Re: It Can Happen to You

#206

Post by TeMPOraL »

est31 wrote: post #174
CGamesPlay wrote: post #72

Earlier quoted context omitted.

And maybe, in a decade or so, the man page for these functions will list their algorithmic complexity! That was the most interesting takeaway from this article, for me at least. I have only seen a one or two libraries that actually list this in their documentation.

The cppreference page linked by the blog post has been changed since: https://en.cppreference.com/w/cpp/io/c/fscanf#Notes > Note that some implementations of sscanf involve a call to strlen, which makes their runtime linear on the length of the entire string. This means that if sscanf is called in a loop to repeatedly parse values from the front of a string, your code might run in quadratic time

Good. I'm so happy they put it there. It's a little thing, but such little things - documenting corner cases - can have great benefits.

I have a bad memory for all but most frequently used standard library calls, so I regularly end up refreshing my memory from cppreference.com, and I tend to instinctively scan any notes/remarks sections, as there's often critical information there. So now I can be sure I'll be reminded of this the next time I need to use scanf family.

Re: It Can Happen to You

#207

Post by ctoth »

ineedasername wrote: post #101
johnfn wrote: post #32

Loving the progression here. Tomorrow, someone’s going to reduce the boot times of macOS by 90% by the same principle. A week from now, someone will prove P=NP because all the problems we thought were NP were just running strlen() on the whole input.

That's actually a very simple one. Just run a regex on "P != NP" to remove the "!" and you're good to go.

Seriously the most I have laughed in like 6 months. Which probably says a lot more about me than this joke. I know that jokes aren't really welcome on HN, and I generally really like this policy. But just had to mention this was just ... what I needed to read right now.

Re: It Can Happen to You

#208

Post by TeMPOraL »

beaconstudios wrote: post #11
decasia wrote: post #5

It would be nice if it were more common for standard library functions to include algorithmic complexity as part of the standard documentation. Absent that, of course we can potentially read the source code and find out, but I think for the most part we tend to operate based on an informed assumption about what we imagine the algorithmic complexity of a given operation would be. Inevitably, sometimes the assumption i…

personally, I think I wouldn't even bother to check the algorithmic complexity of every external function I call. I'd just use the logical choice (like sscanf) and only consider optimising if things started to slow down and profiling the application highlighted it as a bottleneck.

I personally would, if it was listed in documentation. Doing stuff and profiling later is the right general approach to performance optimization. But what's better is not doing stupid mistakes in the first place, if they are trivial to avoid. To achieve that, you need to know the complexity guarantees of functions and data structures - or at least their ballpark (like, "this could be O(n) or perhaps O(n logn), definitely not worse").

This is where setting the guarantees and documenting them is useful - it allows people to trivially avoid making these performance mistakes. Prevention is better than cure, in that - as GTA Online case demonstrates - in the latter stage of product development, people may not bother fixing performance anymore.

Re: It Can Happen to You

#209

Post by kaba0 »

quelsolaar wrote: post #142
tux3 wrote: post #15

The moral of the story, as far as I'm concerned: do NOT parse strings in C! Use a library, prefferably in a higher-level language. C string handling is a mess of viciously surprising APIs, juggling those particular footguns is almost certainly not your least bad option.

Wouldn't this be an argument to go in the opposit direction? If you are using high level functionality that you dont know the implementation details of, you are running the risk of unintended consequences. I am a C programmer who have implemented string to number parsing for this very reason. I know exactly what it does and how fast it is. If you do use code you didn't write, The chance of a standard library being po…

I think it goes both ways in that you either go full low level and write yourself everything (for questionable benefits), or you use a (possibly higher level) language with sane standard library, but the important thing is the quality of said library.

Re: It Can Happen to You

#210

Post by tom_mellior »

Years ago I was working on a compiler frontend that was capable of reading multiple files into one program representation, as opposed to compilers that compile each input file completely separately. At some point we were trying to compile some project made up of many small files, and our frontend got very slow. However, when we concatenated all those files into one big source file, everything went smoothly.

I investigated. It turned out that we were keeping some sort of global symbol table structure. It was updated after parsing each file, something like this (the original was C++, but this is pseudocode because I can't be bothered):

    list global_symbol_table;

    void update_symbol_table(list new_symbols) {
        global_symbol_table.add_all(new_symbols);
        // Keep sorted so we can do efficient lookups with binary search.
        sort(global_symbol_table);
    }
For N files, this meant N calls to sort() on a list that grew linearly in N, so having something like O(N^2 log N) complexity overall.

This has a few problems:

1. Even if you want to use a "sorted list" representation, it would suffice to sort the new symbols only (the global table is always sorted by its invariant) and do a merge of the sorted list.

2. But really, you want a set data structure that does the same thing better.

3. But also, could we maybe speed up the lookups in some other way? I looked around for the uses of this global symbol table and found... none. We were keeping data around and updating it in the least efficient manner imaginable, without ever using that data.

I deleted the above function and the global symbol table, and performance was back to expected levels.

Post reply on HN