LINUX.ORG.RU

Оптимальная структура данных

 


1

1

Имеется таблица из трех колонок. Первая — просто номер строки. Во второй и третьей — целые числа. Пример:

1 3 2

2 4 3

3 4 2

4 5 3

5 6 3

и т.д. Пары чисел, образованные второй и третьей колонками, не повторяются. Но по отдельности могут повторяться, как в примере. Нужно по номеру строки получать числа из колонок и наоборот: по заданной паре найти номер строки. Какая структура данных лучше всего для этого подходит? Наивным вариантом был бы массив пар, тогда a[i].up, a[i].low давали бы числа во второй и третьей колонках из строки i. Но в этом случае неудобно искать в обратную сторону, то есть по паре получать индекс.

★★★★

Заведи два контейнера, для поиска в одну сторону и в другую.

Gvidon ★★★★
()

какие либо ещё ограничения на данных есть?

например в приведённом примере колонка up у тебя упорядоченны по не убыванию

если это действительно то обратное - по паре номер можно бинарём по up-колонке

--- если заранее известен диапазон одной из колонок то можно сделать синтетический ключ - пусть A-диапазон колонки, а а и б значения тогда можно хранить какое либо уподядочение по синтетическому ключу б*A+а и значении номер строки - и каким либо способом(зависящий от метода хранения таких пар(синтетика,номер_строки))- быстро(не менление логарифма опятьже ну и переходе на линейный поиск на дюжине вроде)

anonymous
()

Классическая структура связи «многие-ко-многим» © — пример таблицы о пиве.

quickquest ★★★★★
()

я бы использовал 2 hash tables (в некоторых ЯП - ассоциативные массивы, словари и тд).

  1. key: номер строки, value: пара чисел
  2. соотвественно наоборот:)
uglym8
()

остортированyый по парам массив (если тебя поиск в основном интересует)

получение по индексу = O(1)

получение индекса по паре - O(log(n))

НО вставка O(n)

anonymous
()

а это смотря как вы используете (планируете использовать) сию таблицу. От этого и зависит которое измерение первое.

при работе с СУБД как правило удобнее ориентироваться на строки - там данные прилетают и требуются как правило строками/наборами;

при работе с экспериментальными и расчётными данными - на столбцы - там обычно отдаёшь/получаешь готовые массивы/срезы по столбцам.

А лучше сделать вдоль - написать интерфейс под который подстроить и тот и другой способ организации конечных данных и не заботится про пустяки до первого stable.

MKuznetsov ★★★★★
()

Как в базах данных: массив пар и обратный индекс к нему.

urxvt ★★★★★
()

Нужно по номеру строки получать числа из колонок

Делаешь массив

uint8_t arr[][2] ={{3,2}, {4,3}, {4,2}, {5,3}, {6,3}};
Первая колонка — вообще незачем ее хранить.

наоборот: по заданной паре найти номер строки.

Надо сцепить пары таким образом, чтобы одно целое число было. Например, в случае uint8_t у нас каждое число занимает 1 байт. Пара соотвественно 2 байт. Ну, очевидно

size_t map[] = {
  [(3<<8) | 2] = 0,  [(4<<8) | 3] = 1, 
  [(4<<8) | 2] = 2,  [(5<<8) | 3] = 3,
  [(6<<8) | 3] = 4
}
см. https://gcc.gnu.org/onlinedocs/gcc-6.3.0/gcc/Designated-Inits.html

И таким образом, если сделать обращение к массиву map[(4<<8) | 2] то там будет индекс массива для arr[][2]

Только первая колонка отсуствует, и там вся индексация будет начинаться с 0 а не с 1, но это думаю не особо критично

SZT ★★★★★
()
Последнее исправление: SZT (всего исправлений: 2)
Ответ на: комментарий от SZT

Или даже как-нибудь так

size_t map[256][256] = {
  [3][2] = 0,  [4][3] = 1, 
  [4][2] = 2,  [5][3] = 3,
  [6][3] = 4
};
Но вообще возникает резонный вопрос: а пары могут повторятся в том смысле, что одна пара это например 2, 3 а другая 3, 2, или это будем считать одной и той же парой?

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

Но вообще возникает резонный вопрос: а пары могут повторятся в том смысле, что одна пара это например 2, 3 а другая 3, 2, или это будем считать одной и той же парой?

Можно считать, что первое число в паре всегда больше второго, как в примере.

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

В таком случае можно кое-что заоптимизировать, ключевые слова triangular matrix, треугольная матрица

Я когда-то такое на Си реализовывал, в общем суть там такая, что отображение

(0,0) -> 0, (1,0) -> 1, (1,1) -> 2,
(2,0) -> 3, (2,1) -> 4, (2,2) -> 5,
(3,0) -> 6, (3,1) -> 7, (3,2) -> 8,
(3,3) -> 9, (4,0) ->10, (4,1) ->11
и я под это даже формулу вывел, давно это было. И так можно использовать одно число для хранения пары

SZT ★★★★★
()
Последнее исправление: SZT (всего исправлений: 1)
Ответ на: комментарий от SZT

Если пары никогда не одно число т.е. не может быть (0,0), (1,1) то тоже можно вывести формулу для такого отображения. Я в Maxima делал

SZT ★★★★★
()

разрешите с тривиальным решением влезть. спасибо =)

class MyTable:
    def __init__(self, s):
        self.forward = {}
        self.backward = {}
        for l in s.split('\n'):
            if l.strip():
                n, a, b = (int(x) for x in l.split())
                self.forward[n] = a,b
                self.backward[a,b] = n
    
    def __getitem__(self, key):
        if type(key) is int:
            return self.forward[key]
        else:
            return self.backward[key]

s = '''
    1 3 2
    2 4 3
    3 4 2
    4 5 3
    5 6 3
    6 32768 65536
'''

tab = MyTable(s)

print(tab[6])
print(tab[32768,65536])
$ python mytab.py
(32768, 65536)
6
anonymous
()
Ответ на: комментарий от hotpil

та то два ассоциативных массива просто

anonymous
()
Ответ на: offtop от Aswed

Ммм, для программирования

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