Suppose we have sorted array of strings e.g. std::vector<std::string> or some other elements with string as key - for example std::vector<std::pair<std::string,data_type>.

Normally to find element there, we need to do binary search.

It will work fast, but each comparison will have pointer indirection plus relatively expensive string comparison.

To speedup things, we can do something like this:

struct small_string{
   char data[8];

std::vector<small_string> line;

When we populate normal vector, we can populate first 8 characters in line array.

Then we do normal binary search, but we check line array first. If we get "equal" we check in normal array. Else we proceed with binary search.

I did this already. Speed up is between 30 and 50 %.

However, because many of values in line array could be same, we can do hash-table or array and store first and last index from the array.

It could look like this:

struct small_string_range{
   char data[8];
   size_t begin_range;
   size_t end_range;

std::vector<small_string_range> range_line;

// for non C++ programmers, size_t is unsigned integer

The structure now resembles trie, to search inside first you locate first 8 bytes of the key inside range_line. You do that using hash-table of binary search.

Second you check ranges and do binary search on normal array. For keys less than 8 bytes, you get index directly.


Is this existing algoritm?

Is this algorithm viable?

  • 3
    If all data values are 32 characters long and all start with same 8 characters then there will be 0 speed up. It appears that this is similar to indexing. – Farrukh Subhani Nov 3 '17 at 11:25
  • 5
    Yes, it seems like you're indexing a lot of strings based on first 8 characters. To see if its viable we need to understand what your problem actually is; your question lacks context for us to be able to answer that. Another thing: isn't this the same as using a "std::unordered_multimap<char[8], std::unordered_map<std::string, MyClass>>"? – Emerson Cardoso Nov 3 '17 at 11:45
  • 3
    You were doing OK until you actually asked your questions at the bottom, neither of which is answerable. "Is this an existing algorithm" is... well, I'm not sure why that's relevant. The answer to "Is this algorithm viable" is "does it fulfill your needs?" – Robert Harvey Nov 3 '17 at 14:53
  • @FarrukhSubhani you are right, but in this case, the "line index" will not do harm. It will return whole range. – Nick Nov 3 '17 at 16:16
  • 2
    Absent any specific requirements, whatever algorithm you have now is already good enough. – Robert Harvey Nov 3 '17 at 18:06