быстрый индекс для “содержит строку”

После долгих размышлений и экспериментов у меня есть ответ!

Сначала мы добавляем 4-ю точку к каждому треугольнику, чтобы сделать их тетраэдрами с объемным центроидом. Мы рассчитываем объемы и центры масс и умножаем их друг на друга, чтобы получить наши моменты. Мы суммируем моменты и разделим на общий объем, чтобы получить наш общий центроид.

Мы рассчитываем объемы, используя детерминированный метод, показанный здесь (уравнение 32): http://mathworld.wolfram.com/Tetrahedron.html

Центроиды каждого из тетраэдров являются просто средним значением точек 4.

Хитрость заключается в том, что из-за способа создания STL-файла треугольники имеют нормаль, которая указывает наружу от поверхности детали, следуя правому правилу 3 вершин, используемых для создания треугольника. мы можем использовать это в своих интересах, позволяя нам иметь согласованное соглашение, в котором можно определить, должен ли объем тетраэдра быть добавлен или вычтен из нашей чистой части (это связано с тем, что выбранная нами опорная точка может не обязательно находиться внутри детали, и общая деталь не обязательно является выпуклой, однако является замкнутым объектом).

Используя метод определения для вычисления объема, первые три точки координат будут представлять три точки нашего треугольника. Четвертый пункт будет нашим общим происхождением. Если нормаль создана треугольником (следуя правому правилу, идущему из пункта 1 , 2 , 3) указывает на нашу общую точку отсчета, этот объем будет рассчитан как не часть нашего общего твердого тела, или отрицательный объем (указывая на, я имею в виду вектор, созданный нормалью треугольника, указывает на ту же сторону, что и нормальная плоскость, созданная вектором от нашей опорной точки до центроида тетраэдра). Если вектор направлен в сторону от опорной точки, то это положительный объём или внутри детали. Если он нормальный, то объём переходит в ноль, так как треугольник находится в той же плоскости, что и опорная точка.

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

В любом случае, рассматривает код (его даже более простой, чем объяснение).

class data // 3 vertices of each triangle
{
public:
    float x1,y1,z1;
    float x2,y2,z2;
    float x3,y3,z3;
};

int main ()
{
    int numTriangles; // pull in the STL file and determine number of triangles
    data * triangles = new triangles [numTriangles];
    // fill the triangles array with the data in the STL file

    double totalVolume = 0, currentVolume;
    double xCenter = 0, yCenter = 0, zCenter = 0;

    for (int i = 0; i < numTriangles; i++)
    {
        totalVolume += currentVolume = (triangles[i].x1*triangles[i].y2*triangles[i].z3 - triangles[i].x1*triangles[i].y3*triangles[i].z2 - triangles[i].x2*triangles[i].y1*triangles[i].z3 + triangles[i].x2*triangles[i].y3*triangles[i].z1 + triangles[i].x3*triangles[i].y1*triangles[i].z2 - triangles[i].x3*triangles[i].y2*triangles[i].z1) / 6;
        xCenter += ((triangles[i].x1 + triangles[i].x2 + triangles[i].x3) / 4) * currentVolume;
        yCenter += ((triangles[i].y1 + triangles[i].y2 + triangles[i].y3) / 4) * currentVolume;
        zCenter += ((triangles[i].z1 + triangles[i].z2 + triangles[i].z3) / 4) * currentVolume;
    }

    cout << endl << "Total Volume = " << totalVolume << endl;
    cout << endl << "X center = " << xCenter/totalVolume << endl;
    cout << endl << "Y center = " << yCenter/totalVolume << endl;
    cout << endl << "Z center = " << zCenter/totalVolume << endl;
}

Чрезвычайно быстрое вычисление центров масс для файлов STL.

Вы можете начать с просмотра trie . Хотя они в основном используются в качестве деревьев префиксов, сама структура данных может быть адаптирована для более быстрого общего поиска.

Можно создать индексы Permuterm .

Для «struve» следует вставить в дерево Radix (или дерево поиска общего назначения):

struve$
truve$s
ruve$st
uve$str
ve$stru
e$struv
$struve

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

Вы говорите, что у вас миллионы коротких строк, поэтому я предполагаю, что вы не можете хранить их в оперативной памяти и хранить в базе данных. Предположим, что вы храните свои "короткие строки" в таблице с именем my_string (id, string). Создадим другую таблицу, назовем ее my_substring (id, substring[unique]), содержащую каждую подстроку каждой строки в my_string. Также создадим соединительную таблицу для двух вышеуказанных таблиц: my_substring_to_string (id, substring_id, string_id), содержимое которой, я полагаю, очевидно.

Теперь поиск прост и быстр: ищите свою подстроку в my_substring (не забудьте создать индекс на my_substring.substring) и присоединяйте ее к my_string через my_substring_to_string.

Добавление и удаление новой короткой строки потребует обновления в my_substring и my_substring_to_string, но это довольно просто.

Если это решение приведет к появлению таблицы my_substring с неприемлемо большим размером, то ее можно оптимизировать. Вместо того, чтобы держать каждую подстроку, старайтесь держать каждый суффикс и искать 'substring%' с помощью ilike. Например, если слово 'blues', то необходимо хранить суффиксы: 'blues', 'lues', 'ues', 'es', 's' (соединенные с 'blues'). Тогда поиск 'lu' (ilike 'lu%') будет совпадать с 'lues'. Таким образом, база данных все равно будет использовать индекс, созданный в колонке my_substring.substring, так что поиск все равно будет быстрым.

Если последовательности имеют произвольную длину и произвольный подсчет, можно попробовать алгоритм Ахо-Корасика , который прост в реализации и масштабируется на O (n) длины поискового текста, и выполняет поиск по всем последовательностям одновременно.

Если количество искомых последовательностей невелико, попробуйте использовать алгоритмы Horspool , которые исключительно легко реализовать и которые в среднем меньше O (n) в последовательность.

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

Обычно это выполняется с помощью модуля struct в Python. Она позволяет извлекать значения из упакованных двоичных представлений, определяемых последовательностями спецификации формата.

При использовании двоичного ввода-вывода данные загружаются в последовательность, а затем распаковываются с помощью struct.unpack ().

После долгих размышлений и экспериментов у меня есть ответ!

Сначала мы добавляем 4-ю точку к каждому треугольнику, чтобы сделать их тетраэдрами с объемным центроидом. Мы рассчитываем объемы и центры масс и умножаем их друг на друга, чтобы получить наши моменты. Мы суммируем моменты и разделим на общий объем, чтобы получить наш общий центроид.

Мы рассчитываем объемы, используя детерминированный метод, показанный здесь (уравнение 32): http://mathworld.wolfram.com/Tetrahedron.html

Центроиды каждого из тетраэдров являются просто средним значением точек 4.

Хитрость заключается в том, что из-за способа создания STL-файла треугольники имеют нормаль, которая указывает наружу от поверхности детали, следуя правому правилу вершин 3, используемых для создания треугольника. мы можем использовать это в своих интересах, позволяя нам иметь согласованное соглашение, в котором можно определить, должен ли объем тетраэдра быть добавлен или вычтен из нашей чистой части (это связано с тем, что выбранная нами опорная точка может не обязательно находиться внутри детали, и общая деталь не обязательно является выпуклой, однако является замкнутым объектом).

Используя метод определения для вычисления объема, первые три точки координат будут представлять три точки нашего треугольника. Четвертый пункт будет нашим общим происхождением. Если нормаль создана треугольником (следуя правому правилу, идущему из пункта 1 , 2 , 3) указывает на нашу общую точку отсчета, этот объем будет рассчитан как не часть нашего общего твердого тела, или отрицательный объем (указывая на, я имею в виду вектор, созданный нормалью треугольника, указывает на ту же сторону, что и нормальная плоскость, созданная вектором от нашей опорной точки до центроида тетраэдра). Если вектор направлен в сторону от опорной точки, то это положительный объём или внутри детали. Если он нормальный, то объём переходит в ноль, так как треугольник находится в той же плоскости, что и опорная точка.

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

В любом случае, рассматривает код (его даже более простой, чем объяснение).

class data // 3 vertices of each triangle
{
public:
    float x1,y1,z1;
    float x2,y2,z2;
    float x3,y3,z3;
};

int main ()
{
    int numTriangles; // pull in the STL file and determine number of triangles
    data * triangles = new triangles [numTriangles];
    // fill the triangles array with the data in the STL file

    double totalVolume = 0, currentVolume;
    double xCenter = 0, yCenter = 0, zCenter = 0;

    for (int i = 0; i < numTriangles; i++)
    {
        totalVolume += currentVolume = (triangles[i].x1*triangles[i].y2*triangles[i].z3 - triangles[i].x1*triangles[i].y3*triangles[i].z2 - triangles[i].x2*triangles[i].y1*triangles[i].z3 + triangles[i].x2*triangles[i].y3*triangles[i].z1 + triangles[i].x3*triangles[i].y1*triangles[i].z2 - triangles[i].x3*triangles[i].y2*triangles[i].z1) / 6;
        xCenter += ((triangles[i].x1 + triangles[i].x2 + triangles[i].x3) / 4) * currentVolume;
        yCenter += ((triangles[i].y1 + triangles[i].y2 + triangles[i].y3) / 4) * currentVolume;
        zCenter += ((triangles[i].z1 + triangles[i].z2 + triangles[i].z3) / 4) * currentVolume;
    }

    cout << endl << "Total Volume = " << totalVolume << endl;
    cout << endl << "X center = " << xCenter/totalVolume << endl;
    cout << endl << "Y center = " << yCenter/totalVolume << endl;
    cout << endl << "Z center = " << zCenter/totalVolume << endl;
}

Чрезвычайно быстрое вычисление центров масс для файлов STL.

Вы можете начать с просмотра trie . Хотя они в основном используются в качестве деревьев префиксов, сама структура данных может быть адаптирована для более быстрого общего поиска.

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

Обратите внимание, что я не имею в виду "список", чтобы означать "связанный список", а просто "некая последовательная структура данных", что обычно означает вектор....