да, ив одном 10Мб файле двух одинаковых фамилий не пропустит - а из двух пропустит, вы об этом не подумали? ТАК ваша задача не решается.
Namer Вам 200 разных файлов по 10мб рассортировать, или один большой разбить на 200 и отсортировать как единое целое? Ошибок в своей логике не замечаете?
мда... Как и писал мне надо сравнить два больших файла. А разбивка на маленькие и сортировка их - это мой запасной вариант на случай если по-человечески никто не сделает. Короче время вышло. Мне на днях нужен результат. Поэтому сделаю сам как умею. Такую фигню превратили в холивар. Тема закрыта.
Говорил же я - не сделаешь. И был прав. В твоём варианте с 30 * 30 файлов при 900 операциях открытия указателей будет свыше триллиона лишь на участок из 15 сегментов с одной из сторон. Сколько их будет при 30 указателях с обоих сторон - посчитай сам. Кроме того ты не получишь желаемого результата этим алгоритмом, потому что в нем неправильная логика =) А уж о том, сколько он будет отрабатывать, я молчу, бгг.
У мой брат Билло - дибилизм. Как раз для шутка! 2Namer не спи - замерзнешь. Пораскинь мозгами и все станет понятно. Даю наводку. Тысячи людей пишут БД движки и за большие деньги и это целая НАУКА. Именно потому что пару десятигиговых файлов просто так НЕ СРАВНИШЬ не только без БД (это вобще дохлый номер, можешь не париться даже) но и с помощью БД тоже НЕ СРАВНИШЬ =) Именно поэтому в БД наличествуют индексы и индексы это тоже целая наука, и твой заказчик если хочет получить применимый в реальности результат - ему стоит раскошелиться на ssd денег за триста американских рублей + сервак ну с гигами четырьмя оперативки, выделенной только под эту задачу. тогда и только тогда это сравнение, поиск и прочее ковыряние будет занимать секунды. никаким другим образом на файлах ты этот вопрос решить получив приемлемый результат - не можешь. Просто потому что НА КАЖДОЕ сравнение у тебя без использования индексов будет уходить две минуты минимум на хардах и чуть по-меньше на ssd. помножь это на количество необходимых сравнений и ты получишь капец какое большое число. при этом при пихании в БД такого количества барахла надо отключать запись кей-файла до конца импорта, иначе пипец. соответственно необходимо построить структуру конвейера так, чтобы не пихать каждый раз в БД эту уйму данных заново, а только вносить изменения и добавлять. А донести все это своему заказчику - это твоя работа. И если он не хочет этого понять - ну его к черту. Ибо других вариантов у тебя НЕТ =)
Ну в плане алгоритмической задачи с уклоном в дрочилово оптимизации задача очень даже интересна, подбирать методы работы с файлами, иметь ограничения по памяти, разбираться с хеш-таблицами. Я бы сделал, но нифига не на пхп, на чем нибудь более низкоуровневом. Но не буду зависит от реализации В принципе если операция редкая то можно и подождать тупо O(n^2) операций. Если данные редко (относительно) изменяются то есть смысл их упорядочить, а при внесении сразу в нужное место помещать, тогда поиск в лоб перебором можно заменить бинарным поиском, что дико прибавит в скорости (в среднем ). Короче много там возможностей для извращенного мозга
antonn тоныч, ты такой смешной иногда... посчитай на калькуляторе сколько придется ждать. даже если разосрать скорость чтения до 100мб в сек, то на на 10 гб уйдет 100 сек. =) это НА КАЖДУЮ строку если строка размером в килобайт, то в 10 гигах таких строк будет: 10 000 000. умножь на сто секунд... Это 31 год, хули =) дааа... можно подождать разок...
hash-tables Ну и плюс кеширование блоками (в памяти оно как бы на порядки быстрее), все реально сделать, но "в лоб" будет просто долго (из-за подгрузки кусков файлов и выгрузки временных данных на винт, если вдруг 2Гб памяти будет мало). Разумеется это не на пхп делать надо. я это делал, последнее на чем я забил была виртуальная файловая система, обычный бинарный файл с кластерной структурой (блоками в разных местах файла можно было инфу писать), даже с дефрагментатором, с ограничением на файл в 8Гб. Тока там не тупо по строкам читая блоки надо было пробежать и еще я сильно сомневаюсь что автор не преувеличил размеры, сколько там мильярдов фамилий будет? ЗЫ при бинарном поиске тебе не надо будет читать файл подряд, кстати. А если по нему индексы соорудить и разместить их в памяти... (впрочем если у автора именно такие фамилии на 10Гб то сами индексы займут не сильно меньше)
Да, недавно меряли скорость чтения из файла строк, на аппаратном рейде1 330Мб файл прочитался с разбивкой на строки за 0,9 секунды Думаю понятно в что тут уперлось в скорость чтения и можно ли еще ускорить А сравнение в памяти куска данных на 512Мб со скоростями от полу-гигабайта в секунду (это без оптимизаций) не сильно затратно, упрется в подгрузку блока (сколько там по 100Мб подгружать? 31 год говоришь в результате? ) ) и хранение промежуточных результатов.
короче без индексов это сделать не возможно. даже на ссд рейде даже если скорость вырастет в сто раз, все равно выходит месяца четыре на один тупопроход. Индексы, оперативка, защита от сбоев электричества и от сбоев рейда. Вот можно тогда работать =)
смотря что понимать под "индексами", их механизм пасплывчатый, ну и не 31 год же точно)) ну часов 5-6 пошуршит и наверное все точно переберет ему. я бы в sqlite закинул, или FB. чиста поржать))) Автор, скажи честно сколько весят файлы и какие в них данные я не верю в 10Гб списка фамилий, это бредогенератор какой-то
А нельзя ли сделать несколько стеков из списков, и отсортировать любой удобной сортировкой ваши файлы?))) Просто у меня была задача в институте сделать стек и его сортировку простым выбором, стек я легко организовал из списка))) В стеке было от 1000 до 100000 значений сортировка 100000 значений занимала простым выбором 3-4 минуты если память не изменяет, может чутка больше для сортировки простым выбором требуется ещё 2 доп стека! Да и вообще как бы сортировка файлов есть, если уж такие огромные которые в память не помещаются))) Тока непонятно зачем его в память то кидать всегда считал что при сортировке юзал память ток для переменных куда кидались значения, как то даже не думал файл с N-кол-вом строк туда запихнуть!)) Может стоит решить проблему нормально исходя из того как надо это сделать, а не как проще или как получается, потому что сделать по другому знаний не хватает?)
31 год это если сравнивать в тупую построчно файл в 10 гигабайт, исходя из размера строки в один килобайт. 10 000 000 на 10 000 000 итераций * 1024 байта / на скорость чтения с диска. =)
100к по 32 символа (чего не во всякой фамилии есть) это примерно чуть больше трех мегабайт. Тут вообще тупо перебором можно без всяких хеш-таблиц сделать. Потому и сомневаюсь про гигабайтные файлы с фамилиями, этож сколько их там. ну и как бы нужно самому со стеками не вылететь за 2Гб по памяти
Ну это я просто привёл задание которое у меня было в пример! Тобишь если взять метод сортировки более быстрый и оптимальный то всё будет очень быстро, а по поводу 2-х файлов надо как бы уметь разделять задачи, помойму всё просто таким заданиям на первом курсе учат, не в миллион строк конечно, но сути не меняет, учат общему подходу! Общий подход таков: берём 2 файла проверяем их сначала поиском на совпадение и формируем 3 файл без совпадений данных это очень просто помойму всё, а потом сортируем 3 файл! Покажите мне где тут проблема? Может я слепой или программировать разучился? :lol:
проблема в том, что данные файлы не влазят в память, нужно обрабатывать их по частям, но как единое целое. решение "в лоб", как ты предлагаешь, занимает ориентировочно 2 суток (50 часов) по любому не будет очень быстро - по-мойму это разъясняется в предыдущих постах
Ахахахаха... этапять. А ты когда умел то? Вали дальше своим говнокодом торговать. Gromo И ты хорош, нашел себе компетентного собеседника. Еще бы с поповым посоветовался ))
Я не говорю что их надо пихать в память! В память помещаются же только значения переменных и ссылки на них, а весь файл так и остаётся на диске! Мож я просто неправильно изъясняю свою мысль, но решение может быть и в лоб, но рабочее, скорость конечно нельзя с нормальной БД сравнить! Но тут другой вопрос нафига было доводить ТХТ файл до 2 гигов! Все давно поняли, что ты главный ТРОЛЛЬ этого форума, не надо это доказывать на каждом шагу, надоедает! :lol:
Фух, сделал Как и говорил на файлах. sqlite привлекаю только для сортировки полученных маленьких файлов. Кому интересно, на сортировку одного 2ГБ файла уходит до 3-х часов. Для рнр мне кажется нормально и меня вполне устраивает. На ночь зарядил, а утром результат Файлы рулят Не зря где-то читал, что гугл тоже отказался от хранения инфы в БД, а использует для этого плоские файлы, так гораздо быстрее.
Namer Вот меня тоже интересовал вопрос, но боялся задать, а то вдруг тролли прибегут)) В БД 2 гб если загнать, мне кажется тоже не особо быстро будет сортироваться или я ошибаюсь? Сколько примерно времени уходит на сортировку в БД такого объёма?