Горе от LLM ума
Понадобилось мне в качестве хобби иметь в хозяйстве программу, которая должна уметь следующее:
по данным двум текстовым файлам, одному длиннее, другому короче, она должна находить такое смещение в первом файле, начиная с которого его строки наиболее точно совпадают со строками второго файла, причем строки последнего, состоящие из одной звёздочки, считаются совпадающими с любой строкой.
В моём случае более длинный файл - от силы десяток тысяч строк, более короткий - редко когда более тысячи строк, поэтому наивный O(n*m) алгоритм мне бы годился, просто писать было лень. Но я в промпте это не сказал, и получил от Cerebras программу на Питоне, которая пользовалась этим алгоритмом только в качестве крайнего случая, если не был доступен NumPy.
А если NumPy был доступен, то программа каждой уникальной строке, встретившейся в обоих файлах, ставила в соответствие случайное комплексное число длины 1, кроме *, для которой брался 0. Потом она строила соответствующие массивы чисел, удлиняя при необходимости до степени 2, причем для второго массива числа брались сопряжённые, и делала всему этому делу FFT со всеми возможными смещениями от 0 до разницы длин файлов.
В конкретных деталях алгоритма я не разбирался, но мотивировалось это тем, что для совпадающих строк произведение чисел будет равно в точности вещественному 1, а для несовпадающих - произвольным комплексным числам со случайным Re, в среднем равным нулю. Так как нас интересуют только нетривиальные совпадения, то совпадения со звёздочкой, сиречь умножения на 0, общий результат не изменяют.
Потом в массиве полученных результатов находился максимум, и его индекс объявлялся искомым смещением.
Этим всем делом Cerebras был очень горд, потому что вычислительная сложность получалась меньше, типа O((n+m)*log(nm)) или что-то в таком духе.
Ну и, короче, в тех случаях, когда реальное совпадение было стопроцентным, этот алгоритм с хорошей вероятностью выдавал правильное смещение, хотя и с рейтингом заметно меньше 1 (обычно около 0.8-0.9), а для совпадения с погрешностями результат был произвольным и непохожим на реальность. Пришлось подавить это безобразие, закомментировав "import math", и всё заработало ровно так, как я хотел.
по данным двум текстовым файлам, одному длиннее, другому короче, она должна находить такое смещение в первом файле, начиная с которого его строки наиболее точно совпадают со строками второго файла, причем строки последнего, состоящие из одной звёздочки, считаются совпадающими с любой строкой.
В моём случае более длинный файл - от силы десяток тысяч строк, более короткий - редко когда более тысячи строк, поэтому наивный O(n*m) алгоритм мне бы годился, просто писать было лень. Но я в промпте это не сказал, и получил от Cerebras программу на Питоне, которая пользовалась этим алгоритмом только в качестве крайнего случая, если не был доступен NumPy.
А если NumPy был доступен, то программа каждой уникальной строке, встретившейся в обоих файлах, ставила в соответствие случайное комплексное число длины 1, кроме *, для которой брался 0. Потом она строила соответствующие массивы чисел, удлиняя при необходимости до степени 2, причем для второго массива числа брались сопряжённые, и делала всему этому делу FFT со всеми возможными смещениями от 0 до разницы длин файлов.
В конкретных деталях алгоритма я не разбирался, но мотивировалось это тем, что для совпадающих строк произведение чисел будет равно в точности вещественному 1, а для несовпадающих - произвольным комплексным числам со случайным Re, в среднем равным нулю. Так как нас интересуют только нетривиальные совпадения, то совпадения со звёздочкой, сиречь умножения на 0, общий результат не изменяют.
Потом в массиве полученных результатов находился максимум, и его индекс объявлялся искомым смещением.
Этим всем делом Cerebras был очень горд, потому что вычислительная сложность получалась меньше, типа O((n+m)*log(nm)) или что-то в таком духе.
Ну и, короче, в тех случаях, когда реальное совпадение было стопроцентным, этот алгоритм с хорошей вероятностью выдавал правильное смещение, хотя и с рейтингом заметно меньше 1 (обычно около 0.8-0.9), а для совпадения с погрешностями результат был произвольным и непохожим на реальность. Пришлось подавить это безобразие, закомментировав "import math", и всё заработало ровно так, как я хотел.
