C ++ Просмотр столбцов данных - PullRequest
Новая
       6

C ++ Просмотр столбцов данных

1 голос
/ 14 февраля 2012

У меня есть файл данных, который является МАССИВНЫМ, и я не могу загрузить все это в память, чтобы просмотреть его. Как я могу отсортировать файл в поисках определенных значений (это широта, долгота, высота, и я ищу два значения высоты, которые ограничивают определенную высоту, которые я буду интерполировать вокруг, чтобы найти конкретные точки широты / долготы)? Я могу прочитать каждую строку с помощью «getline ()», но это не позволит мне взглянуть на два значения и сравнить их с моим конкретным значением, которое я хочу (насколько я знаю).

Спасибо.

Ответы [ 2 ]

0 голосов
/ 14 февраля 2012

Вы пытаетесь найти две последовательные линии / строки, между которыми высота пересекает целевое значение? В этом случае вы можете просто сохранить предыдущую высоту между итерациями getline(). Затем, на любой линии, если текущая высота больше цели, а предыдущая меньше цели, или наоборот, вы пересекли целевую высоту и выведите все, что вам нужно вывести (возможно, сохранить всю предыдущую строка, чтобы вы могли интерполировать широту / длину).

0 голосов
/ 14 февраля 2012

  • Поскольку ваш файл относительно небольшой, вы можете разбить его на 4 файла по 250 МБ и искать в них.

  • Считывать небольшие фрагменты из файлов и искатьвнутри этих кусков для ценностей.Это линейное время.

  • Сортировка файла.Вы можете легко сделать это, читая маленькие порции и сортируя каждый порцию с помощью быстрой сортировки (это делается на месте).После того, как чанк отсортирован, выведите его на диск.После того, как все чанки отсортированы и на диске, начните читать несколько значений из каждого чанка и удерживать их в памяти (вызовите эти new_chunks). Затем начните объединять значения вместе в больший файл.Всякий раз, когда значения из new_chunk используются и перемещаются в больший файл, кэшируйте больше из их соответствующего исходного, теперь srted, чанка.После завершения этого процесса у вас должен быть отсортированный файл.Это немного улучшает поиск, но вам все равно придется выполнять линейный поиск, перенося части большого отсортированного файла в память, так что это также линейное время.

  • Лучший способ - после того, как вы отсортировалифайл, как в шаге выше, то есть индексы в памяти.Сопоставить индекс с местоположением в файле / на диске.Таким образом, вы можете улучшить время поиска в файле.

    Например, если ваши файлы имеют номера, такие как 1,2,3, ... 100.Индексируйте файл, сохраняя в памяти (число в файле: позиция в файле / позиция на диске) 1: 0,10: 9,20: 19 ... Теперь, если вы ищете номер 18, вы выполняете двоичный поиск вэти индексы (время входа в систему), и вы обнаружите, что 18 находится между 10 и 20, поэтому вы читаете файл в позициях с 9 по 19 и переносите этот кусок в память.Теперь выполните другой двоичный поиск в этом чанке: время logm

    Общее время выполнения: logn + logm или log (num_index_chunks) + log (avg_size_of_chunk) + chunk_i_load_time

...