C++ записывает список имен в файл в определенном порядке, не загружая их все в память
У меня есть школьное задание загрузить список имен из одного текстового файла в другой, упорядочивая их, но мне не разрешается хранить их все в памяти (например, в массиве) одновременно. Что было бы лучшим способом сделать это. Я должен сделать бинарный поиск по ним потом.
Моей первой мыслью было сгенерировать хеш-ключ для каждого из них, а затем записать их в месте, соответствующем их ключу, но тот факт, что я должен выполнить бинарный поиск впоследствии, заставляет меня думать, что это избыточно. Проблема в том, что они не знают их заранее (это означает, что мне нужно как-то нажать на некоторые имена в середине).
3 ответа
Это, наверное, самый простой способ
1) прочитайте файл построчно и найдите имя в вашем методе сортировки
например
-читаемое имя_1.
-читать следующее имя_2.
Если имя_1 <имя_2, то имя_2 = имя_1 и повторите.
2) прочитайте файл построчно и найдите второе имя. т.е. самое низкое имя, которое все еще выше, чем имя.
3) записать имя в файл.
4) Теперь прочитайте построчно для третьего имени
5) добавить второе имя в файл и т.д...
Это не будет быстро, но у него не будет виртуальной памяти. У вас никогда не будет более 3 имен, хранящихся в памяти.
Несколько способов:
1) Вы можете разбить данные на несколько временных файлов; сортировать каждый файл отдельно; объединить файлы.
2) вызвать операционную систему для сортировки файла, что-то вроде
system ("sort input>output")
Хорошо, я не знаю, использовал ли я термин "лексическое дерево" прямо в своем комментарии, но я бы сделал дерево, похожее на двоичное, но не только с двумя возможными узлами, но и с целым алфавитом. Я считаю, что это называется "Три".
В узлах вы держите счетчик, сколько записей закончилось на этом конкретном узле. Вы создаете узлы динамически по мере необходимости, поэтому потребление места остается на низком уровне.
Затем вы можете пройти по всему дереву и получить все элементы в порядке. Это было бы нетривиальным видом, который очень хорошо работал бы для записей с общими префиксами. Это было бы быстро, так как все вставки линейны, траверса также линейна. Так что это займет O(2*N), где N количество символов во всем наборе для сортировки. И потребление памяти было бы хорошо, если бы у набора данных были общие префиксы.