Как получить группу имен с одинаковыми первыми буквами из отсортированного по алфавиту списка?

Question

Мне было интересно, как лучше всего получить группу имен по первой букве. Настоящее приложение, в котором я работаю, написано на javascript, но иногда у меня была похожая проблема на другом языке. Одна идея, о которой я подумал, - это выполнить бинарный поиск конца имен из определенной буквы, а затем выполнить еще один бинарный поиск для начала. Другая идея состояла в том, чтобы взять отношение расстояния заданной буквы от начала и применить это отношение, чтобы найти, где начать поиск. Например, если буква была «е», тогда я начинаю четверть пути по списку и выполняю какой-то поиск, чтобы увидеть, насколько я близок к нужной букве. Программа будет работать с несколькими сотнями имен, поэтому я действительно не хотел просто делать цикл for и искать все это. Кроме того, мне интересно, какие существуют алгоритмы для этого?

Answer 1

Оба ваших подхода имеют свои преимущества и недостатки. Бинарный поиск дает точно O (log (N)) сложность, и ваш второй метод даст приблизительно O (log (N)) с некоторым преимуществом для равномерного распределения имен и, возможно, недостатком для другого типа распространения. Что лучше, зависит от ваших потребностей.

Одно большое улучшение, которое я могу предложить, это для индексации позиций символов при создании списка имен . Сделайте простую хэш-карту с первыми буквами в качестве ключей и начальными позициями в качестве значений. Это займет O (N), но только один раз, и тогда вы получите точное положение для каждой буквы в постоянное время. Для JavaScript вы можете сделать это, например, при загрузке данных на страницу, когда вы все равно проходите по списку.

Answer 2

Ребята, я думаю, мы могли бы использовать подход, подобный сортировке count. Мы могли бы создать массив размером 26. Этот массив не был бы обычным массивом, но был бы массивом указателей на связанный список, который имеет следующую структуру.

Узел структуры { char * ptr; struct node * next; };

struct node * names [26]; // Наш массив.

Теперь мы просканировали бы список за O (n) раз и соответствовали бы первому символу, который мы могли бы вычесть 65 (если ASCII-значение буквы находится в диапазоне 65 - 90). Ребята, я вычитаю 65, чтобы исправить письмо в массиве 26 размеров. В каждом месте мы можем создать связанный список и можем хранить соответствующие слова в этом месте.

Теперь предположим, что если мы хотим найти все буквы, которые начинаются с буквы D, мы могли бы напрямую сделать это для расположения в массиве 3 (не нужно снова применять хэш-функцию), а затем проследовать связанный список, созданный до достижения нулевого значения.

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

Answer 3

Имена имеют забавный способ неравномерного распределения по алфавиту, поэтому вы, вероятно, не выиграете столько, сколько надеетесь, предсказав, где искать.

Но действительно простой способ сократить ваш поиск в среднем на два шага заключается в следующем: если буква находится в диапазоне от a до m, бинарный поиск следующей буквы. Затем выполните двоичный поиск от начала списка только до позиции, которую вы только что нашли для следующей буквы . Если буква от n до z, найдите ее в двоичном формате. Затем, снова, ищите только часть списка после того, что вы только что нашли.

Стоит ли экономить два шага? Не знаю. Это довольно легко реализовать, но опять же, два шага не занимают много времени. (Правильное предположение, что письмо спасет вас, может быть, в лучшем случае 4 шага.)

Другая возможность состоит в том, чтобы иметь начальные ячейки для каждой буквы. Он начинается уже отсортированным, и если вам нужно выполнить повторную сортировку, вам нужно выполнить сортировку только по одной букве, а не по всему списку. Недостатком является то, что если вам нужно часто манипулировать всем списком, вы должны склеить все корзины вместе.

Answer 4

Если у вас несортированный набор имен файлов, я бы предложил следующий алгоритм:

1) Создайте две переменные: 1) текущая найденная первая буква (я назову ее currentLetter ) 2) список имен файлов, которые начинаются с этой буквы ( 1010 * currentFilenames *)
2) firstLetter = null
currentFilenames = [] - пустой список или массив
3) Перебирать имена файлов. Если текущие имена файлов начинаются с currentLetter, добавьте это имя к currentFilenames. Если он начинается с буквы, которая идет перед currentLetter, тогда присвойте currentLetter первой букве нового имени файла и создайте новый список currentFilenames, который состоит только из одного текущего имени файла.

При таком алгоритме у вас будет в конце буква, которая идет первой в алфавите, и список файлов, начинающихся с этой буквы.

Пример кода (пытался писать в Javascript, но не вините, если я что-то написал неправильно):

function GetFirstLetterAndFilenames(allFilenames) {
    var currentLetter = null;
    var currentFilenames = null;

    for (int i = 0; i < allFilenames.length ; i++) {
        var thisLetter = allFilenames[i][0];
        if (currentLetter == null || thisLetter < currentLetter) {
            currentLetter = thisLetter;
            currentFilenames = [allFilenames[i]];
        } else if (currentLetter == thisLetter) {
            currentFilenames.push(allFilenames[i]); 
        }
    }

    return new {lowestLetter = currentLetter, filenames = currentFilenames};
}

Answer 5

Если план состоит в том, чтобы что-то сделать с именами (вместо того, чтобы просто узнать, сколько их), то необходимо будет отсканировать имена, которые соответствуют критериям соответствия первой букве.Если это так, то кажется, что бинарный поиск по имени во всем наборе является самым быстрым методом.Часть «сделать что-то» будет включать сканирование имен, начиная с местоположения, найденного двоичным поиском.Когда прочитано имя, которое больше не начинается с данной буквы, все готово.