I have lists on different pages:

1. Title 1 2. Title 2 2.1. Title 2.1 (Новый список на новой странице). 2.2 Title 2.2 3. Title 3

When you switch the keyboard arrow between the elements of the list, a text description of the element appears next to the window.

Each element of the list is assigned a tag (array of tags, char* ), by which the description of the element of the list is searched. Tags are compared with the strcmp() function.

How can I reduce the search time for a tag in an array, if I use one array and there will be many elements in it? After all, more time is being compared. The idea was to use different arrays of tags for different lists, that is, each list would need to be assigned an id and use several arrays. What else can be implemented? Language: Clean C.

  • Are you sure that search time is critical? Even if you have a linear search, the cost of it is usually much less than, say, waiting for keyboard input. Maybe you have a strcmp in a loop? - VladD
  • @VladD in a for loop compares the text of the active element of the list with each element of the array. If the element is at the end of the array, you will have to wait until the entire array passes, - Maxim Gusev
  • And what is the size of the array? Although approximately? Ten items? Thousand? Million? - VladD
  • 300 items. Strings. - Maxim Gusev
  • 300 line comparisons should be instant, in theory. And what is the length of the string? (Maybe you have a string with which you compare, does not end with \0 by mistake?) - VladD

1 answer 1

If time is critical - after completing data loading, sort the array of tags in any not the slowest way (by sorting Shell for example), then look for the string in the array using binary search.

For example:

 long int searchBinary(dio_table *t, const requestData *rdata) //t - структура с массивом указателей на строки и их количеством, rdata - данные для поиска { lint bottom = 0; // Индекс начала поиска lint mid = 0; lint top = t->head.count - 1; //Индекс конца поиска while(bottom <= top){ mid = (bottom + top)/2; int cmpr = strcmp (t->lines[mid].data, rdata->col); //t->lines[mid].data получаем строку по середине, сравниваем с rdata->col if (cmpr == 0){ // Если нашли искомую строку, то ее и возвращаем return mid; } else if (cmpr > 0){ // Если сравнение вернуло положительное число, значит искомая строка где-то выше по списку top = mid - 1; } else if (cmpr < 0){ // Или ниже bottom = mid + 1; } } return -1; // Если ничего не нашли }

That's about it.

But I repeat:

 Такой поиск работает ТОЛЬКО в отсортированном массиве!

UPD: array sorting should be ascending

  • I would argue that this is optimal for finding a string, here the complexity is O (ln (count) * lenght) and using boron or hash tables is possible for O (length). Truth and more memory will be used. - pavel
  • @pavel with complexity you have gone too far, but in terms of speed, the hash table can be really faster. And maybe not :) - The_Netos