Более быстрый способ поиска списка?

Я пытаюсь сделать свою программу более эффективной, и я считаю, что исправление этого линейного поиска будет очень полезно с точки зрения скорости, но мне любопытно, как бы я изменил это на нечто вроде двоичного поиск, поскольку я считаю, что список не обязательно упорядочен. Есть ли способ упорядочить список на основе его первого аргумента key?Более быстрый способ поиска списка?

Что я работаю в настоящее время:

int* key_sequences::data(int key){ 
    for(it=myList.begin(); it!=myList.end(); ++it){ 
     if(it->first==key){ 
      return &(it->second[0]); 
     } 
    } 
    return nullptr; 
};

источник

2016-10-20 Gman

Двоичный поиск невозможен без сортировки. –

Очевидным ответом было бы прекратить использование списка и заменить его более подходящей структурой данных (возможно, «map» или 'unordered_map', из внешнего вида вещей). В зависимости от того, когда/как часто происходит вставка/удаление, вы можете также рассмотреть «FlatMap» - двоичный поиск в отсортированном массиве. –

Часто последовательность последовательно повторяется, для последовательных клавиш. Кэширование последнего результата поиска может затем сократить общее время от O (n²) до O (n). Но я бы изменил структуру данных на что-то более подходящее, например «карта». –

Поиск в просто связанного списка O (п), где n является размер списка.

Однако в некоторых реализациях люди используют три указателя списка, один в начале, один в середине и один в конце, так что при поиске появляется - они могут ускорить процесс, поэтому вы можете искать в Интернете для это.

НО, если бы я был вами и был так интересен в ускорении поиска, я бы попробовал другую структуру данных (hash? Like std::unordered_map) или отсортировать список.

источник

2016-10-20 20:06:17 gsamaras

Более быстрый способ поиска списка?

ответ

Смежные вопросы