LINUX.ORG.RU
Форум — Development  

Найти закономерности в массиве


0

5

Есть массив (или файл) состоящий из 32-х разрядных чисел. Пример: 

1
2
7
8
7
8
7
8
2
7
8
7
8
7
8
4
В массиве есть одинаковые последовательности и под-последовательности. Нужно их найти и свернуть. Пример выхода: 
1
repeat 2:
  2
  repeat 3:
    7
    8
4

Колличество таких уровней вложенности - не ограничено, нужно найти их все.

Причем элементов в массиве около 2 миллионов, так что переборные алгоритмы должны былть поинтеллектуальнее.

Время работы алгоритма особо не критично, несколько минут вполне устроит.

★★★★

Последнее исправление: alexru (всего исправлений: 1)

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

Zenom ★★★
()

Интересная задача. Проблема в том, что не существует однозначного решения.

12312321321

То ли делать 2×(123)+21321, то ли 12312+2×(321). Эффективность одинаковая.

Если не решать задачу именно оптимальной свёртки, то достаточно выявить сначала одиночный повторения, затем двойные и так далее.

ZhAN ★★
()
Ответ на: комментарий от ZhAN

Да, я подозревал, что однозначного решения нет. Устроит любое решение, даже может быть и не самое оптимальное.

alexru ★★★★
() автор топика
Ответ на: комментарий от AIv

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

alexru ★★★★
() автор топика

Во первых, алгоритм должен быть рекурсивный, те. нужно представлять в массиве не только числа но и свернутые последовательности с пред прохода. Тогда можно применять алгоритм до тех пор, пока хоть что то сворачивается.

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

Как то так...

AIv ★★★★★
()
Ответ на: комментарий от AIv

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

AIv ★★★★★
()
Ответ на: комментарий от AIv

Спасибо, завтра попробую.

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

alexru ★★★★
() автор топика

Используй математические пакеты (например Maple) там есть подобные функции, но на память их названия не подскажу.

trex6 ★★★★★
() 
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace App
{
    class Program
    {
        static IEnumerable<string> ToLines(IEnumerable<object> list, int spaces = 0)
        {
            foreach (object obj in list)
            {
                string pre = string.Join(string.Empty, Enumerable.Repeat(" ", spaces));

                if (obj is int)
                    yield return pre + obj;
                else
                {
                    var kvp = (KeyValuePair<int, List<object>>)obj;
                    yield return string.Format("{0}repeat {1}:", pre, kvp.Key);
                    foreach (string line in ToLines(kvp.Value, spaces + 4))
                        yield return line;
                }
            }
        }

        static IEnumerable<object> Process(IEnumerable<object> source, int depth)
        {
            var list = new List<object>(source);
            var result = new List<object>(list.Count);

            for (int startIdx = 0; startIdx < list.Count; ++startIdx)
            {
                var counts = Enumerable.Repeat(0, depth).ToList();

                for (int rangeLen = 1;
                     rangeLen <= depth && startIdx + rangeLen <= list.Count;
                     ++rangeLen)
                {
                    int count = 0;
                    bool eq;

                    do
                    {
                        ++count;
                        eq = true;

                        for (int i = 0; i < rangeLen; ++i)
                        {
                            int idx0 = startIdx + i;
                            int idx1 = startIdx + rangeLen*count + i;

                            if (idx1 >= list.Count)
                            {
                                eq = false;
                                break;
                            }

                            if ((int)list[idx0] != (int)list[idx1])
                            {
                                eq = false;
                                break;
                            }
                        }
                    } while (eq);

                    counts[rangeLen - 1] = count;
                }

                int max = counts.Max();
                int maxDepth = counts.IndexOf(max) + 1;

                if (max == 1)
                    result.Add(list[startIdx]);
                else
                {
                    var subList = new List<object>(maxDepth);

                    for (int i = 0; i < maxDepth; ++i)
                        subList.Add(list[startIdx + i]);

                    subList = Process(subList, depth).ToList();
                    result.Add(new KeyValuePair<int, List<object>>(max, subList));
                    startIdx += maxDepth * max - 1;
                }
            }

            return result;
        }

        static void Main()
        {
            const string inputFileName = @"input.txt";
            const string outputFileName = @"output.txt";
            const int maxDepth = 100;

            var source = (from line in File.ReadAllLines(inputFileName)
                          select (object)int.Parse(line.Trim())).ToList();

            var result = Process(source, maxDepth);
            File.WriteAllLines(outputFileName, ToLines(result));

            foreach (var line in ToLines(result))
                Console.WriteLine(line);

            Console.ReadKey();
        }
    }
}
anonymous
()
Ответ на: комментарий от anonymous

Если нужны подробности, реализация на питоне или чём-либо другом и т.п. Стучись в аську: 959693. Недорого :)

anonymous
()
Ответ на: комментарий от anonymous

Вообще говоря метод Main лучше переписать вот так: [code] static void Main() { const string inputFileName = @«C:\Users\NightmareZ\Desktop\input.txt»; const string outputFileName = @«C:\Users\NightmareZ\Desktop\output.txt»;

var source = (from line in File.ReadAllLines(inputFileName) select (object)int.Parse(line.Trim())).ToList();

var result = Process(source, source.Count); File.WriteAllLines(outputFileName, ToLines(result));

foreach (var line in ToLines(result)) Console.WriteLine(line);

Console.ReadKey(); } [/code]

anonymous
()
Ответ на: комментарий от anonymous

Вообще говоря метод Main лучше переписать вот так: 

static void Main()
{
    const string inputFileName = @"input.txt";
    const string outputFileName = @"\output.txt";

    var source = (from line in File.ReadAllLines(inputFileName)
        select (object)int.Parse(line.Trim())).ToList();

    var result = Process(source, source.Count);
    File.WriteAllLines(outputFileName, ToLines(result));

    foreach (var line in ToLines(result))
        Console.WriteLine(line);

    Console.ReadKey();
}

Два миллиона значений обрабатывает за считанные десятки секунд.

anonymous
()

Если данные случайны, то вероятность больших вложенностей стремится к нулю. Будут срабатывать только вложенности первого порядка и длины 1-2 символа. Тогда это обычный алгоритм кодирования длин серий.

mclaudt ☆
()
Ответ на: комментарий от anonymous

Еще нет, пока другие проблемы всплыли, код не пробовал и не смотрел еще.

alexru ★★★★
() автор топика

Ввиду полной неоднозначности решения здесь надо писать программку на генетических алгоритмах. Целевая функция: минимум длинны последовательности после рекурсивного применения набора подстановок.

psv1967 ★★★★★
()
Ответ на: комментарий от psv1967

хочешь поговорить о них? это простая штука ты должен понять

Не хочу.

Хочу, чтобы народ (и ты в том числе) не светился в темах с конкретными вопросами в роли Капитана Очевидности и его многочисленных родственников.

Или приводи рабочий код, или GTFO. Ибо поставленная задача была решена до твоего высера.

anonymous
()
Ответ на: комментарий от anonymous

1 насчет «была поставлена задача» ты меня позабавил, пиши еще мой смелый анонимный друх, (правда не удобно ходить нюхать темы без извещения?)

2 ничего решено не было, сворачивание последовательности имеет _много_ вариантов. код моего решения очевиден при использовании любой библиотеки ГА.

3 писать, приседать и танцевать я буду когда мне захочется. но ты давай, выдавай хотелки дальше :) напомню что тему экономно поместили не в раздел «работа»

4 ну и кроме того никто не привел задавая вопрос те самые данные. а после _твоего высера_ действительно уже и не актуально.

ЗЫ это ты что провоцируешь что бы потерли сообщения?

psv1967 ★★★★★
()
Ответ на: комментарий от Eddy_Em

Там картинки только, где код?

Лучше даже, имхо, было бы спросить: «где код, решающий задачу данной темы?»

anonymous
()
Ответ на: комментарий от Eddy_Em

Про это я вначале спрашивал :)

Извиняюсь. Я этот момент пропустил :)

anonymous
()
Ответ на: комментарий от psv1967

Вот реальные данные: http://dl.dropbox.com/u/6121480/ga_evaluation_data.zip (настоящие цифры замененны их более короткими эквивалентами без изменения структуры)

До задачи у меня руки еще так и не дошли, так что решение еще актуально. Особенно с ГА интересно посмотреть будет.

alexru ★★★★
() автор топика
Ответ на: комментарий от psv1967

>хочешь поговорить о них? это простая штука ты должен понять

Ну ни и нахера ты тут вспомнил про генетические алгоритмы? Сраный ЛОР катится в сраное говно =(

Waterlaz ★★★★★
()
Ответ на: комментарий от alexru

я так понял в job никто тему переносить не собирается?

тогда к данным теперь попрошу формулировку задачи, то что написано в начале топика можно трактовать как угодно

например:

1 27 87878 27 87878 4 1 278 7878 278 78 78 4

«нужно найти их все» (С)

сформулируйте конкретней что Вы хотите найти, почему я должен догадываться за Вас? в чем критерий свертки именно так как указано у Вас?

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

Что касается ГА. Упаковать данные можно многими способами, даже если будет наконец выбран критерий что Вы считаете за «правильную» упаковку. Осуществить поиск вариантов будет нереально ибо это комбинаторика.

Не вижу никаких проблем запускать даже стандартную библиотеку ГА хоть рекурсивно хоть итеративно (хоть запустить параллельно два процесса эволюции обменивающихся словарем, это вообще стандартное решение) пополняя словарь подстановок.

Но задача наиболее красиво подходит для генетического программирования. Задача простая вырастить программу генерирующую заданную последовательность. В ней всего то операторов «повторить заданную строку заданное число раз» и «объединить две строки в одну». Но критерий все равно нужен, таких программ очень много получится.

psv1967 ★★★★★
()
Ответ на: комментарий от psv1967

я так понял в job никто тему переносить не собирается?

Зачем?

1 27 87878 27 87878 4 1 278 7878 278 78 78 4

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

Ну и дальше идет стандартная мантра любителей ГА - много абстрактного текста и никакой конкретики.

Не позорьтесь.

alexru ★★★★
() автор топика
Ответ на: комментарий от alexru

> > я так понял в job никто тему переносить не собирается?

Зачем?

чего? ну там цену вывесят, или наймут велосипедостроителя ...

Что это?

это мега форматирование по умолчанию

1 2(27 87878) 4

Чем этот вариант неправильный и почему? Сколько таких вариантов есть в последовательности надо объяснять?

PS «В топике четко указано» смеялся :) так еще и формат вывода такой делать? :)

PPS я уже просто не жду услышать какую неземную структуру отражает такая запись исходной последовательности длинной в хрен знает сколько экранов даже в одном своем варианте.

ЗЗЗЫ Ну и дальше идет стандартная мантра неосиляторов ГА - много пафоса текста и никакой конкретики.

Не позорьтесь.

psv1967 ★★★★★
()
Ответ на: комментарий от psv1967

Чем этот вариант неправильный и почему? Сколько таких вариантов есть в последовательности надо объяснять?

Мы уже давно выяснили, что решение неоднозначно. Правильная версия такой светрки будет «1 2(27 2(87) 8) 4», меня устроит.

PPS я уже просто не жду услышать какую неземную структуру отражает такая запись исходной последовательности длинной в хрен знает сколько экранов даже в одном своем варианте.

И не услышишь - это секрет.

Да, я неосилятор ГА, так как никакой реальной пользы от ГА я еще не видел.

alexru ★★★★
() автор топика
Ответ на: комментарий от alexru

> Мы уже давно выяснили, что решение неоднозначно. Правильная версия такой светрки будет «1 2(27 2(87) 8) 4», меня устроит.

ну это тупик

раз ты не можешь объяснить критерий по которому выбрана конкретная свертка, то никакого поиска оптимального решения невозможно.

Да, я неосилятор ГА, так как никакой реальной пользы от ГА я еще не видел.

о да! например весь мир структуру нейрональных сеток оптимизирует именно ГА, куча софта за мегабаксы, а ты не видишь пользы...

И не услышишь - это секрет.

ну ну... «у нас есть такие приборы» :)

поскольку мне не интересно делать велосипед (а смысла в таком преобразовании исходного ряда я не вижу ни какого) -> тратить на это свободное время не интересно

psv1967 ★★★★★
()
Ответ на: комментарий от psv1967

раз ты не можешь объяснить критерий по которому выбрана конкретная свертка, то никакого поиска оптимального решения невозможно.

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

поскольку мне не интересно делать велосипед (а смысла в таком преобразовании исходного ряда я не вижу ни какого) -> тратить на это свободное время не интересно

Слив засчитан.

alexru ★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development