Задача на оптимизацию поиска

@stream · Регистрация: 19.11.2011

Студворк — интернет-сервис помощи студентам

Есть такая задача. Даны два текстовых файла в формате [код 8 цифр],[строка 14 символов]. Необходимо создать третий файл в котором объедены строки из первых файлов, если у них одинаковые коды.(по идее выполняется inner join)
Пример.
Первый файл
00000001 AAAAAAAAAAAAAA
04532323 CCCCCCCCCCCCCC

Второй файл
00000001 BBBBBBBBBBBBBB
04532323 DDDDDDDDDDDDDD
Результат
00000001 AAAAAAAAAAAAAA,BBBBBBBBBBBBBB
04532323 CCCCCCCCCCCCCC,DDDDDDDDDDDDDD

Нужно написать самым эффективным способом, использую не более 50 MB JVM heap. Кто может подсказать литературу, чтобы там были подобные задачи решены?

@Qwertiy · 19.09.2013, 11:56

Используй HashMap.

Добавлено через 1 минуту
Уточнение. Если в файлах строки уже упорядочены, то оптимальнее просто мёрджить, как в сортировке слиянием.

Добавлено через 49 секунд
И вообще, память программы ты называешь, а ограничения на количество данных - нет. Странным не кажется?

@Igor3D · 19.09.2013, 12:57

Отсортировать оба масива по "коду", а затем просто идти по одному массиву и сразу писать. Т.е. взяли строку из первого, находим все с таким же кодом во втором, на плюсах это std::equal_range

@Qwertiy · 19.09.2013, 13:23

Сортировка даст O(n*lb(n)), а хэш-таблица O(n)...

Добавлено через 1 минуту
Кстати, в си я бы использовал map - тоже n*lb(n), хотя сортировка вероятно была бы немного быстрее.

@stream · 19.09.2013, 13:45 **[ТС]**

Как раз моим рабочим вариантом был HashMap c выталкиваем уже встречавшихся значений. Но при рамере кучи 50 метров выдается сообщение Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
PS в каждом файле 10000000 записей.

@Qwertiy · 19.09.2013, 15:48

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

Добавлено через 4 минуты
Хотя нет, есть более оптимальный вариант (возможно). Сделать некоторую хэш-функцию, отображающую индекс в int приемлимого диапазона и хранить данные о номерах записей, в которых оно встречается. И читать требуемые записи, чтобы проверить, совпадает ли id. Но тут опять проблемы с доступной памятью, надо хранить что-то другое...

@Igor3D · 19.09.2013, 16:41

Сообщение от Qwertiy

Сортировка даст O(n*lb(n)), а хэш-таблица O(n)...

Там не сказано что ключ/код уникальный, а тогда hash теряет свою прелесть..

@Qwertiy · 19.09.2013, 17:27

Сообщение от Igor3D

Там не сказано что ключ/код уникальный

Там сказано что надо слить по ключу. Соответственно значение в таблице - не одна запись. Т. е. HashMap<Integer, List<String>>.
В любом случае, информация о числе записей в файлах означает, что это в память не влезет никакое решение, требующее держать все данные в памяти.

Новые блоги и статьи Все статьи Все блоги /
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .

@stream 0 / 0 / 1 Регистрация: 19.11.2011 Сообщений: 26

	Задача на оптимизацию поиска 18.09.2013, 23:22. Показов 747. Ответов 7 Метки нет (Все метки) Есть такая задача. Даны два текстовых файла в формате [код 8 цифр],[строка 14 символов]. Необходимо создать третий файл в котором объедены строки из первых файлов, если у них одинаковые коды.(по идее выполняется inner join) Пример. Первый файл 00000001 AAAAAAAAAAAAAA 04532323 CCCCCCCCCCCCCC Второй файл 00000001 BBBBBBBBBBBBBB 04532323 DDDDDDDDDDDDDD Результат 00000001 AAAAAAAAAAAAAA,BBBBBBBBBBBBBB 04532323 CCCCCCCCCCCCCC,DDDDDDDDDDDDDD Нужно написать самым эффективным способом, использую не более 50 MB JVM heap. Кто может подсказать литературу, чтобы там были подобные задачи решены? 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	19.09.2013, 11:56
	Используй HashMap. Добавлено через 1 минуту Уточнение. Если в файлах строки уже упорядочены, то оптимальнее просто мёрджить, как в сортировке слиянием. Добавлено через 49 секунд И вообще, память программы ты называешь, а ограничения на количество данных - нет. Странным не кажется? 0

@Igor3D 1967 / 823 / 114 Регистрация: 01.10.2012 Сообщений: 4,831 Записей в блоге: 2
	19.09.2013, 12:57
	Отсортировать оба масива по "коду", а затем просто идти по одному массиву и сразу писать. Т.е. взяли строку из первого, находим все с таким же кодом во втором, на плюсах это std::equal_range 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	19.09.2013, 13:23
	Сортировка даст O(nlb(n)), а хэш-таблица O(n)... Добавлено через 1 минуту* Кстати, в си я бы использовал map - тоже n*lb(n), хотя сортировка вероятно была бы немного быстрее. 0

@stream 0 / 0 / 1 Регистрация: 19.11.2011 Сообщений: 26
	19.09.2013, 13:45 [ТС]
	Как раз моим рабочим вариантом был HashMap c выталкиваем уже встречавшихся значений. Но при рамере кучи 50 метров выдается сообщение Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded PS в каждом файле 10000000 записей. 0

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	19.09.2013, 15:48
	Так это даже один файл просто в память не влезет даже в виде байтового массива. При таком раскладе, единствененный вараинт, который приходит мне в голову, - сортировка слиением для обоих файлов. Насколько я помню, она может быть реализована непосредственно с файлами, без загрузки всех данных в память. Но на быстродействии это естествено скажется отрицательно... Добавлено через 4 минуты Хотя нет, есть более оптимальный вариант (возможно). Сделать некоторую хэш-функцию, отображающую индекс в int приемлимого диапазона и хранить данные о номерах записей, в которых оно встречается. И читать требуемые записи, чтобы проверить, совпадает ли id. Но тут опять проблемы с доступной памятью, надо хранить что-то другое... 0