Если отдельные числа распределены по файлу и не встречаются в большинстве строк, то простая индексация номера строки, в которой они встречаются, может ускорить процесс.Однако это будет медленнее, если ваши данные представляют собой строки с одинаковыми номерами, повторяющимися в разных порядках.
Для построения индекса потребуется только один проход данных по этим строкам:
Hash<int, List<int>> index
line_number = 1
foreach(line in filereader)
{
line_number += 1
foreach(parsed_number in line)
index[parsed_number].append(line)
}
Этот индекс может быть сохранен и повторно использован для набора данных.Для поиска по нему понадобится только что-то подобное.Прошу прощения за смешанный псевдокод, я постарался сделать его максимально понятным.Он «возвращает», когда нет подходящих совпадений, и «возвращает» номер строки, когда все элементы подстроки встречаются в этой строке.
// prefilled hash linking number searched for to a list of line numbers
// the lines should be in ascending order
Hash<int, List<int>> index
// The subsequence we're looking for
List<int> subsequence = {1, 2, 3}
int len = subsequence.length()
// Take all the lists from the index that match the numbers we're looking for
List<List<int>> lines = index[number] for number in subsequence
// holder for our current search row
// has the current lowest line number each element occurs on
int[] search = new int[len]
for(i = 0; i < len; i++)
search[i] = lines[i].pop()
while(true)
{
// minimum line number, substring position and whether they're equal
min, pos, eq = search[0], 0, true
// find the lowest line number and whether they all match
for(i = 0; i < len; i++)
{
if(search[i] < min)
min, p, eq = search[i], i, false
else if (search[i] > min)
eq = false
}
// if they do all match every one of the numbers occurs on that row
if(eq)
{
yield min; // line has all the elements
foreach(list in lines)
if(list.empty()) // one of the numbers isn't in any more lines
return
// update the search to the next lowest line number for every substring element
for(i = 0; i < len; i++)
search[i] = lines[i].pop()
}
else
{
// the lowest line number for each element is not the same, so discard the lowest one
if(lines[position].empty()) // there are no more lines for the element we'd be updating
return
search[position] = lines[position].pop();
}
}
Примечания:
Это может быть тривиально расширено для сохранения позиции в строке, а также номера строки, и тогда только небольшая дополнительная логика в точке «доходности» сможет определить фактическое совпадение, а не только то, что все элементыприсутствуют.
Я использовал «pop», чтобы показать, как он перемещается по номерам строк, но на самом деле вы не хотите уничтожать свой индекс при каждом поиске.
Я предположил, что все числа вписываются в целые числа здесь.Расширьте его до long или даже отобразите строковое представление каждого числа в int, если у вас действительно огромные числа.
Есть некоторые ускорения, особенно при пропуске строк в "поп-этапы, но я пошел за более четким объяснением.
Независимо от того, используя тот или иной метод, вы также можете сократить вычисления в зависимости от данных.Один проход, чтобы определить, является ли каждая строка восходящей, нисходящей, все нечетной, все четной или каковы наибольшее и наименьшее числа, можно использовать для сокращения пространства поиска для каждой подстроки.Будут ли они полезны, полностью зависит от вашего набора данных.