Алгоритм для поиска объединения нескольких строк, сгруппированных по символьному индексу

Я пытаюсь представить эффективный способ определения объединения символов в наборе строк fixed width, сгруппированных по индексу. Что-то вроде этого;Алгоритм для поиска объединения нескольких строк, сгруппированных по символьному индексу

s1 = "013965" 
s2 = "015935" 
s3 = "310012"

В результате в следующем, где существует каждая группа цифр во всех строках с индексом полукокса п:

out = "[03][1][350][90][631][52]"

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

источник

2014-02-13 pondigi

Обычно лучше всего просто получить функциональность, а затем беспокоиться о производительности после того, как у вас есть рабочее решение. Выполняя вещи, наивный путь часто помогает вам видеть места, где можно легко заработать. – Durandal

Биоинформатика профильных матриц Google. Могу дать вам несколько идей. –

Я думаю, что вы не можете сделать намного лучше, чем наивный способ, потому что обычно вам нужно пройти через все позиции всех строк (если в позиции k все цифры 0-9 уже не были). Представьте, что все ваши строки начинаются с 4, а последний начинается с 5, тогда вам нужно пройти 0-позиции всех строк, чтобы не пропустить последнюю строку 5 (которая отличается от этой позиции, чем все остальные). То же самое относится к каждой позиции. –

Если множество всех возможных символов заранее известно, скажем, их число n, с n быть не слишком высокими (например, 10, если вы делаете только цифру), вы можете сделать это путем создания m булева массивы длины n, причем m - количество позиций или цифр во входных строках и n. N-я позиция в m-м массиве будет true, если n-й символ присутствует в m-й позиции в любой из входных строк. False будет означать, что такого персонажа раньше не было в m-й позиции.

Затем вы можете перемещаться по каждой строке, и когда вы сталкиваетесь характер n в положении m вы отмечаете вниз true в п-й позиции т-го массива. В конце концов, вы будете иметь m массивов, каждый из которых описывает содержание м-й группы

pos[0] = {true, true, false, false, false, true, true, false, true, false} 
pos[1] = {true, false, false, false, false, false, false, false, false, false} 
pos[2] = {false, false, true, true, false, false, false, false, false, true}

переводит к

[0,1,5,6,8] [0] [2,3,9]

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

источник

2014-02-13 21:48:18 Warlord

, вторая группа должна быть [0] и третьей [2,3,9] согласно переводам данных сделано в первой группе –

спасибо, мой плохой – Warlord

Алгоритм для поиска объединения нескольких строк, сгруппированных по символьному индексу

ответ

Смежные вопросы