2 ms·
Exactly the opposite... non-random access is extremely common. If you're reading byte X, the odds that you're going to read X+1 are very good. So it makes most
by jerf 6y ago
Exactly the opposite... non-random access is extremely common. If you're reading byte X, the odds that you're going to read X+1 are very good. So it makes most sense to pack them tightly in memory in order, not splash them all over RAM and tie them together with pointers. The latter makes certain things easier, but never by enough on modern hardware to beat the array representation.
- fiddlerwoaroof 6y agoI’m not really talking about access as the computer sees it: most of the code I write that processes strings ends up doing things like splitting at new lines and stripping off the trailing space of each line. Or getting the length of the string or similar things that require efficient access to a semi-arbitrary offset into the string. For the type of string processing code I find myself writing, linked lists are the wrong data structure because they tend to turn O(n) algorithms into O(n^2) ones: this can be mitigated by things like skip-lists, and is complicated by things like Unicode. But, personally, I tend to think that the biggest issue is not the performance impact of non-local storage of the string’s contents (which can be mitigated by techniques like cdr-coding). The problem is that string processing code, in my experience, tends to assume getting a predetermined offset into the string is relatively low cost.