2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Комбинация нескольких чисел в одном
Сообщение10.12.2015, 22:28 


28/11/14
27
Допустим, у нас есть пронумерованные элементы массива. Курсор первого уровня (КПУ) - настоящий номер элемента. Курсор второго уровня (КВУ) - рекурсивная структура, в которой есть один КПУ и один КПУ/КВУ.

Если в качестве операции слияния курсоров использовать сумму, то имели бы примерно такую ситуацию: есть КПУ 1, 2, 4. Первый КВУ $1+2=3$; второй - $4+3=7$ (в моем случае сумма не подходит).

К КВУ ставится два условия: должна быть возможность обратного разложения курсора на его предков (полученный КПУ можно проверить на корректность); КВУ не должен превышать некоторого значения (в целях економии памяти). Глубина рекурсии заранее неизвестна.

Какие есть алгоритмы слияния чисел, удовлетворяющие возникшие условия?

 Профиль  
                  
 
 Re: Комбинация нескольких чисел в одном
Сообщение11.12.2015, 01:11 
Заслуженный участник


26/05/14
981
Пусть КПУ принадлежит диапазону $[0, N-1]$.
Введём операции, которые реализуют стек из КПУ (s - стек, i значение КПУ):
Код:
empty(s)
    return s == 0

push(s, i)
    assert 0 <= i < N
    return s * (N + 1) + (i + 1)

pop(s)
    assert not empty(s)
    return s / (N + 1) # целочисленное деление

top(s)
    assert not empty(s)
    return s % (N + 1) - 1

 Профиль  
                  
 
 Re: Комбинация нескольких чисел в одном
Сообщение11.12.2015, 01:26 


28/11/14
27
В даной ситуации такой вариант не подходит, т.к. N где-то $2^{32}$, а глубина стека может быть больше 100. Для системы расход памяти критический, поэтому диапазон значений КВУ тоже должен быть ограничен (и желательно чтобы он занимал меньше 8 байт)

 Профиль  
                  
 
 Re: Комбинация нескольких чисел в одном
Сообщение11.12.2015, 02:13 
Заслуженный участник


27/04/09
28128
Можно попробовать что-то такое: Есть стандартная функция $f\colon\mathbb N\times\mathbb N\to\mathbb N$ (ноль включаем в натуральные), $f(m, n) = m + \frac{(m+n)(m+n+1)}2$, правда, для её обращения надо считать квадратный корень. Теперь можно отобразить КПУ только на нечётные числа ($a\mapsto 2a+1$), а коды пар — на чётные (умножаем на два), что всегда даст определить, из чего состоит пара. Это универсально, но может не подходить в деталях (например, корень не нравится). Можно использовать тот же подход, но с другой функцией для кода пары. Например, если для хранения компонент пары достаточно $a$ и $b$ бит, можно приписать их друг к другу, а к этому ещё приписать код $a$ (или $b$ — если одна из компонент имеет тенденцию быть короче другой, здесь есть смысл брать соответствующее ей число бит). Код, например, вот такой. Целочисленный sqrt для разбора полученного числа вычислять не понадобится. Если размер каждого поля может быть до 32 бит, и притом того фиксированного — только чётным их числом, можно прямо кодировать $a/2$ четырьмя битами, хотя выглядит всё равно как-то расточительно.

В общем, задача и сама странная. :roll:

 Профиль  
                  
 
 Re: Комбинация нескольких чисел в одном
Сообщение11.12.2015, 09:52 
Заслуженный участник


26/05/14
981
sungmaster в сообщении #1081283 писал(а):
В даной ситуации такой вариант не подходит, т.к. N где-то $2^{32}$, а глубина стека может быть больше 100. Для системы расход памяти критический, поэтому диапазон значений КВУ тоже должен быть ограничен (и желательно чтобы он занимал меньше 8 байт)

Число различных стеков фиксированной высоты $i$ равно $N^i$.
Число различных стеков высоты не более $n$ равно $\sum\limits_{i=0}^{n}N^i = \frac{N^{n+1} - 1}{N - 1}$.
Каждый стек должен быть представлен своим уникальным числом. Для $N = 2^{32}$, $n = 100$ число стеков $\frac{2^{3232} - 1}{2^{32} - 1} \approx \frac{2^{3232}}{2^{32}} = 2^{3200}$.
Такое количество стеков требует для своего размещения $3200 / 8$ байт. Вам нужно 400 байт (на самом деле 401). Или не все стеки могут быть представлены?

 Профиль  
                  
 
 Re: Комбинация нескольких чисел в одном
Сообщение11.12.2015, 10:17 


11/12/14
893
slavav в сообщении #1081320 писал(а):
Вам нужно 400 байт


хуже:

sungmaster в сообщении #1081250 писал(а):
Глубина рекурсии заранее неизвестна.

sungmaster в сообщении #1081283 писал(а):
глубина стека может быть больше 100

 Профиль  
                  
 
 Re: Комбинация нескольких чисел в одном
Сообщение11.12.2015, 11:45 


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

 Профиль  
                  
 
 Re: Комбинация нескольких чисел в одном
Сообщение11.12.2015, 12:14 
Заслуженный участник


26/05/14
981
sungmaster в сообщении #1081337 писал(а):
Вариант, когда размер КВУ растет вместе с ростом глубины рекурсии себя не оправдывает, т.к. в таком случае можно подобрать более адекватный подход для решения задачи. Суть задачи - нужно хранить обратный путь в графе, где в узла может быть нескольо родителей (в моем варианте предполагая, что фиктивный номер узла - это комбинация настоящего номера узла и фиктивного номера родителя)

Несколько мыслей:
1. Если у вас есть эффективный способ хранения номера родителя относительно потомка, то $N$ сильно уменьшается.
2. Если вы хотите хранить сотню элементов готовьте сотни бит.
3. Можно обратный путь хранить прямо в узлах графа, если структура данных и алгоритм позволяют.
4. Можно обратный путь хранить в стеке процедур, если поиск рекурсивный и в каждый момент времени вам нужен только один путь.
5. Нужно больше данных об алгоритме и окружении в котором он должен работать, чтобы продолжать разговор.

 Профиль  
                  
 
 Re: Комбинация нескольких чисел в одном
Сообщение11.12.2015, 13:03 


28/11/14
27
Предположим, что есть такой граф. Он хранит все 3-хбуквенные наборы, содержащие 'a' и 'b'
Изображение
Нужно восстанавливать определенную постедовательность при обходе этого графа (направление обхода особой роли не играет). Указание на то, какую именно последовательность нужно восстановить, приходит с внешним параметром (как вариант - комбинация номеров узлов и их родителей).

Хранение номера родителя в узле не оправдано, если родителей несколько, поскольку всё равно нужно каким-то образом указать, в какому из родителей нужно вернуться.

 Профиль  
                  
 
 Re: Комбинация нескольких чисел в одном
Сообщение11.12.2015, 14:57 


11/12/14
893
sungmaster

Если вкратце, то задача заданная в первом сообщении неразрешима, судя по той информации что вы приводите.
И последняя приведенная информация не позволяет что либо опять таки посоветовать, кроме "полной смены алгоритма".

Рекомендую ознакомится с: http://meta.ru.stackoverflow.com/questi ... xy-problem (прокрутите чуть ниже до "Что такое 'ошибка X-Y'?")

 Профиль  
                  
 
 Re: Комбинация нескольких чисел в одном
Сообщение11.12.2015, 16:21 
Заслуженный участник


26/05/14
981
Попробуем выжать всё что можно из числового стека.
Для каждого узла перенумеруем его предков. Количество предков узла обозначим $v(i)$, где $i$ - номер узла. Я буду нумеровать предков в диапазоне $[0, v(i) - 1]$. Пусть заданы функции abs_pred и rel_pred:
Код:
abs_pred(i, j):
    assert 0 <= i < N
    assert 0 <= j < v(i)
    return ? # абсолюный номер j-ого предка относительно узла i

rel_pred(i, ii):
    assert 0 <= i < N # абсолютный номер потомка
    assert 0 <= ii < N # абсолютный номер предка
    return ? # относительный номер предка ii для узла i

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

Тогда:
Код:
empty(s):
    # получаем номер узла
    i = s % N
    return v(i) == 0 # если нет предков, значит стек кончился

top(s):
    # получаем номер узла
    i = s % N
    return i

pop(s):
    # выталкиваем номер узла
    i = s % N
    s = s / N

    assert v(i) != 0

    # выталкиваем номер предка относительно потомка
    j = s % v(i)
    s = s / v(i)

    # получаем абсолютный номер предка
    ii = abs_pred(i, j)

    # заталкиваем абсолютный номер предка в стек
    s = s * N + ii

    return s

push(s, i):
    assert 0 <= i < N

    # выталкиваем номер узла
    ii = s % N
    s = s / N

    # номер вытолкнутого узла относительно нового узла
    j = rel_pred(i, ii)
   
    # заталкиваем относительный номер
    s = s * v(i) + j

    # заталкиваем абсолютный номер нового узла
    s = s * N + i

    return s

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

 Профиль  
                  
 
 Re: Комбинация нескольких чисел в одном
Сообщение11.12.2015, 16:54 


28/11/14
27
А можно показать работу этого алгоритма на каком-то примере?

aa_dav в сообщении #1081373 писал(а):
Рекомендую ознакомится с: http://meta.ru.stackoverflow.com/questi ... xy-problem (прокрутите чуть ниже до "Что такое 'ошибка X-Y'?")
В даном случае суть вопроса ближе к "что можно забить микроскопом".

Как один из вариантов, можно использовать какой-то алгоритм слияния (хоть и
arseniiv в сообщении #1081289 писал(а):
$f(m, n) = m + \frac{(m+n)(m+n+1)}2$
), потом получать остачу от деления на большое простое число, а при восстановлении угадывать первоначальное число. В нашем случае количество допустимых вариантов воостановления чисел не очень критична, т.к. если у нас будет даже 20 различных вариантов, мы всегда сможем найти нужный (очень маловероятно, что два разных родителя получат одинаковый ключ (или это уже даже ближе к хешу))

 Профиль  
                  
 
 Re: Комбинация нескольких чисел в одном
Сообщение11.12.2015, 17:04 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота

(Оффтоп)

aa_dav в сообщении #1081373 писал(а):
Рекомендую ознакомится с: http://meta.ru.stackoverflow.com/questi ... xy-problem (прокрутите чуть ниже до "Что такое 'ошибка X-Y'?")
Гораздо более понятным (и исторически первым в рунете, насколько я понимаю) описанием "проблемы XY", на мой взгляд, является это: http://www.gunsmoker.ru/2008/10/x-y-z.html

 Профиль  
                  
 
 Re: Комбинация нескольких чисел в одном
Сообщение11.12.2015, 17:28 


11/12/14
893
rockclimber в сообщении #1081413 писал(а):
Гораздо более понятным (и исторически первым в рунете, насколько я понимаю) описанием "проблемы XY", на мой взгляд, является это: http://www.gunsmoker.ru/2008/10/x-y-z.html

Плюсую. И это не оффтоп. Здесь это - не оффтоп.

sungmaster в сообщении #1081410 писал(а):
...потом получать остачу от деления на большое простое число, а при восстановлении угадывать первоначальное число.


Не надо забивать микроскопом. Не надо.

 Профиль  
                  
 
 Re: Комбинация нескольких чисел в одном
Сообщение11.12.2015, 17:47 
Заслуженный участник


26/05/14
981
sungmaster в сообщении #1081410 писал(а):
А можно показать работу этого алгоритма на каком-то примере?

sungmaster в сообщении #1081351 писал(а):
Изображение

Вот примеры путей для узлов. $N = 100$ для наглядности.
Код:
i v(i) стек        s
1   0  1             1
2   1  0,2           2
3   2  0,1,3       103
4   1  0,1,0,4     104
5   2  0,1,0,1,5   305
6   1  0,1,0,1,0,6 306

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group