Поиск одинаковых строк в двух файлах Опции

[*оля*]

А если нужно сравнить 2 текстовых файла и вывести номера строк, которые совпадают, можно использовать этот алгоритм? и если да, то как?

[Lapp]

сравнить 2 текстовых файла и вывести номера строк, которые совпадают

Уточни, пожалуйста: совпадающие строки в разных файлах могут иметь разные номера (например: строка 2 файла 1 и строка 5 файла 2 совпадают), или речь идет о совпадении строк на одной и той же позиции (типа строка 2 в файлах одинаковая)?

[Romtek]

А если нужно сравнить 2 текстовых файла и вывести номера строк, которые совпадают, можно использовать этот алгоритм? и если да, то как?

Нужно использовать алгоритм Diff. Поищи в интернете.

[*оля*]

Уточни, пожалуйста: совпадающие строки в разных файлах могут иметь разные номера (например: строка 2 файла 1 и строка 5 файла 2 совпадают), или речь идет о совпадении строк на одной и той же позиции (типа строка 2 в файлах одинаковая)?

совпадающие строки в разны файлах могут иметь разные номера.

[Lapp]

совпадающие строки в разны файлах могут иметь разные номера.

Гым .
Самое естественное в этой ситуации с моей точки зрения - отсортировать оба файла (сохранив информацию о первоначальных положениях строк) в лексикографическом порядке (скажем, по возрастанию), потом пройтись по ним параллельно и найти, что требуется. Работы полно, короче. С самого начала - неясно, как сортировать: в создавать копию файла или считывать в массив и там орудовать? Первый способ медленный, второй может потребовать много памяти. Что скажешь?

[*оля*]

Гым .
Самое естественное в этой ситуации с моей точки зрения - отсортировать оба файла (сохранив информацию о первоначальных положениях строк) в лексикографическом порядке (скажем, по возрастанию), потом пройтись по ним параллельно и найти, что требуется. Работы полно, короче. С самого начала - неясно, как сортировать: в создавать копию файла или считывать в массив и там орудовать? Первый способ медленный, второй может потребовать много памяти. Что скажешь?

мда, все оказывается не так просто...
Насчет того, что может потребовать много памяти или будет медленнее работать, это не важно, лишь бы работала)
Да, и вправду, логично сначала отсортировать, а потом сравнивать, правда, не совсем уверена, что все хорошо получится, во всяком случае у меня))

[*оля*]

а можно просто каждую строку первого файла поочередно сравнить со всеми строками второго?

[volvo]

Можно, конечно... Как говорила героиня одного фильма "Можно и зайца научить курить" (С). Представляешь, сколько лишних действий ты сделаешь, если будешь постоянно туда-сюда бегать по файлу?

Ты лучше скажи, у тебя файлы большие, или не очень?

[*оля*]

Можно, конечно... Как говорила героиня одного фильма "Можно и зайца научить курить" (С). Представляешь, сколько лишних действий ты сделаешь, если будешь постоянно туда-сюда бегать по файлу?

Ты лучше скажи, у тебя файлы большие, или не очень?

да, я понимаю, но просто не знаю уже как сделать.
ну вообще подразумеваются не маленькие, а что от этого зависит?

[Client]

а что от этого зависит?

Думаю что время выполнения и объем ресурсов.

[*оля*]

Думаю что время выполнения и объем ресурсов.

ну тогда это не столь важно, главное получить результат

[volvo]

Да поймите же наконец, что ресурсы компьютера ограничены!!!

*оля*
Ну, напишешь ты программу, которая будет читать строки из файлов в массивы и работать с ними (либо сортировать оба массива, как предлагал Lapp, либо отсортировать один, и потом бинарным поиском искать в нем строки из второго - не суть важно). Это будет прекрасно работать на маленьких файлах, скажем, по 200 строк. А попытаешься обработать файл из 1000 строк таким образом - что будет? А ничего - вылет из программы с сообщением о нехватке памяти... Это тебе нужно?

Так что определяй, что значит "не маленькие". И озвучь, наконец, каким ты компилятором пользуешься. То, что может один компилятор - для другого может оказаться неприемлемым.

[Lapp]

ну вообще подразумеваются не маленькие, а что от этого зависит?

Работоспособность.

Думаю что время выполнения и объем ресурсов.

Нет, Client. В некоторый момент сумка может порваться, лодка затонуть, селезенка надорваться. нет смысла говорить о "выполнении", если на него требуются годы (или даже дни) либо память 100 Гиг..

[*оля*]

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

Сообщение отредактировано: *оля* - 27.04.2010 14:22

[Lapp]

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

1500 - это как раз вполне терпимо. Если компилятор 32-разрядный, то можно и в памяти сделать.

программы нам разрешают писать только в PascalABC или PascalABC.net

А вот это для меня лично, например, непреодолимое препятствие.. Из-за этого устанавливать эту лабуду я не буду ((. Я использую FPC. Про алгоритм можно продолжать разговоры, но все адаптации к ABC, если они потребуются - сама, пожалуйста. Устраивает?

Оля, я разделяю тему. В следующий раз, пожалуйста, создавай свою тему, а не пость в чужие.

[*оля*]

1500 - это как раз вполне терпимо. Если компилятор 32-разрядный, то можно и в памяти сделать.

А вот это для меня лично, например, непреодолимое препятствие.. Из-за этого устанавливать эту лабуду я не буду ((. Я использую FPC. Про алгоритм можно продолжать разговоры, но все адаптации к ABC, если они потребуются - сама, пожалуйста. Устраивает?

Оля, я разделяю тему. В следующий раз, пожалуйста, создавай свою тему, а не пость в чужие.

ок, в следующий раз буду создавать свою тему)

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

[Lapp]

Нашла статью, в которой сравнивают 2 файла с помощью арифметического кодирования строк числами с плавающей запятой. Но там по-моему все еще сложнее... вроде как расписан алгоритм, но не совсем понятно.

А чем не нравится мой алгоритм?

[volvo]

Оля,
да если у тебя есть возможность использовать PascalABC.NET - там делать нечего... Берешь файл. Один... Построчно читаешь его в переменную типа String, и запоминаешь в List<String> ее хеш. Любой. Скажем, MD5 (с использованием System.Security.Cryptography он вычисляется в 3 строки). А потом открываешь второй файл, и опять же построчно читаешь, вычисляешь для прочитанной строки тот же хеш, и ищешь его в списке.

"Всего и делов то..." (С) "Осенний марафон"

[*оля*]

А чем не нравится мой алгоритм?

не, не в том дело, что он не нравится, просто я не знаю как его реализовать

Добавлено через 10 мин.

Построчно читаешь его в переменную типа String, и запоминаешь в List<String> ее хеш. Любой. Скажем, MD5 (с использованием System.Security.Cryptography он вычисляется в 3 строки).

что-то я не совсем поняла как это сделать(((

[Lapp]

не, не в том дело, что он не нравится, просто я не знаю как его реализовать

а алгоритм volvo? Что в нем неясного?

Для некоторого упрощения: можно просто читать каждую строку из первого файла искать ее во втором.