Ідея для структури даних для зберігання 2D-даних?

У мене є велика 2D сітка, х-х-на-віч. Користувач програми додасть дані про конкретні точки на цій сітці. На жаль, сітка занадто велика, щоб бути реалізованою як великий масив x-by-y, тому що система, на якій вона працює, не має достатньо пам'яті.

Який хороший спосіб це зробити, щоб у пам'яті зберігалися лише ті моменти, які додавали до них дані?

My first idea was to create a BST of the data points. A hash function such as "(long)x<<32 + y" would be used to compare the nodes.

Я тоді зробив висновок, що це може втратити ефективність, якщо це не добре збалансоване, тому я придумав ідею мати BST порівнянних BST пунктів. Зовнішній BST буде порівнювати внутрішні BST на основі їх x значення. Внутрішні BST порівнюють точки за їх y значеннями (і всі вони будуть однаковими x). Тому, коли програміст хоче бачити, чи є точка в (5,6), вони запитають зовнішню BST для 5. Якщо внутрішній BST існує в той момент, то програміст запитає внутрішню BST для 6. Результат бути повернутим.

Чи можете ви думати про будь-який кращий спосіб реалізації цього?

Редагувати: щодо HashMaps: для більшості HashMaps потрібен масив для пошуку. Можна сказати: "data [hash (point)] = point ();" щоб встановити точку, а потім знайти точку шляхом хешування, щоб знайти індекс. Проблема полягає в тому, що масив повинен мати розмір діапазону хеш-функції. Якщо цей діапазон менше, ніж загальна кількість точок даних, які додаються, то вони або не мають місця, або повинні бути додані до переповнення. Оскільки я не знаю кількість балів, які будуть додані, мені доведеться зробити припущення, що це число буде менше певної суми, а потім встановити масив до такого розміру. Знову ж таки, це показує дуже великий масив (хоча він менший, ніж спочатку, якщо припустити, що буде менше точок даних, ніж x * y). Я хотів би, щоб структура мала лінійно масштаб із великою кількістю даних і не займала велику суму, коли вона порожня.

Схоже, що я хочу, це SparseArray, як деякі згадували. Чи застосовуються вони аналогічно тому, що BST є всередині BST?

Edit2: Map<> is an interface. If I were to use a Map then it looks like TreeMap<> would be the best bet. So I would end up with TreeMap< TreeMap< Point> >, similar to the Map< Map< Point> > suggestions that people have made, which is basically a BST inside of a BST. Thanks for the info, though, because I didn't know that the TreeMap<> was basically the Java SDK of a BST.

Edit3: For those whom it may concern, the selected answer is the best method. Firstly, one must create a Point class that contains (x,y) and implements comparable. The Point could potentially be compared by something like (((long)x)<<32)+y). Then one would TreeMap each point to the data. Searching this is efficient because it is in a balanced tree so log(n) cost. The user can also query all of this data, or iterate through it, by using the TreeMap.entrySet() function, which returns a set of Points along with the data.

На закінчення це дозволяє ефективно виконувати і ефективно виконувати розрізний масив, або в моєму випадку, 2D-масив, який також може бути ітераційним шляхом.

8
@ Кіріл Райчев: Після того, як бали додані, я планую використовувати всі дані в структурі для здійснення розрахунків, але не потребують запитів на рівні.
додано Автор Reed B, джерело
@AlexWien: Якщо я використовую примітивний хеш-мап, то мені доведеться натиснути великий масив на стек, як пояснюється моя перша редакція. Це майже як неефективна пам'ять, як використання масиву з прямим зіставленням, тому що обидва вимагають великого простору при запуску. Якщо відображення розподіляється динамічно, то я можу використовувати дуже мало пам'яті, коли є декілька точок (але так, там буде вказівник накладних витрат).
додано Автор Reed B, джерело
Не передивляйтесь колесо, подивіться на структури просторових даних
додано Автор AlexWien, джерело
поки ви не поясните свої операції, його неможливо знайти найкращу структуру. також можливе дерево b з точками в indexed масиві morton. або сітку хешмапів
додано Автор AlexWien, джерело
Гаразд, здається, карта найкраще підходить для вашого використання. Але коли ви потрапляєте в швидкісні проблми космічного простору, подумайте про використання HashMap, який не є об'єктом, що заощаджує 60% вільного простору пам'яті. (точний об'єкт проти примітивних типів)
додано Автор AlexWien, джерело
додано Автор GriffeyDog, джерело
Ви, схоже, більше зацікавлені в основній реалізації структури даних, замість того, як ви збираєтеся її використовувати. Якщо вам потрібні деякі просторові запити (точки з х між 10 і 40) або найближчі запитання сусідів, ви можете використовувати деякі з структур, згаданих AlexWien, або якусь судноплавну карту. Якщо вам потрібно шукати лише певну точку, звичайний старий HashMap буде добре працювати - docs.oracle.com/javase/6/docs/api/java/util/HashMap.html
додано Автор jmruc, джерело

8 Відповіді

Будь Quadtree , k -d-tree або R-дерево .

Магазин індексу до великого масиву точок в одну з просторових структур. Такі просторові структури є вигідними, якщо дані не рівномірно розподілені, як-от географічні дані, що концентруються в містах, і немає сенсу в море.

Подумайте, якщо ви можете забути регулярну сітку, і залишитися з чотирикутного дерева.
(Подумайте, чому вам потрібна регулярна мережа? Регулярна мережа, як правило, тільки спрощення)

За жодних обставин не використовуйте Objects для зберігання точки. Такий об'єкт потребує 20 байт тільки за те, що це об'єкт! Погана ідея для величезного набору даних.

int x [] і int [] y або масиф int [] xy ідеально пов'язані з використанням пам'яті.

Подумайте про читання

Ханан Самет "Основи багатовимірних структур даних"

(принаймні введення).

5
додано
Це хороші структури, але квадрат не найкращий, тому що мої дані розташовуються в окремих рядках і стовпчиках замість точок, розподілених у 2D безперервному домені, яким був розроблений квадрат. Дякую за відповідь!
додано Автор Reed B, джерело
Квадрат не був призначений для безперервних координат. Це для цілих координат, як правило, потужність двох. Так дискретний. Квадратне дерево є індексом, а не самим сховищем. Він використав найближчі точки з мінімальними зусиллями. Ви можете зберігати дані як pints (рядок, колір) або (x, y). чи є ваші дані однаково розподіленими або кластеризовані в деяких точках?
додано Автор AlexWien, джерело
@AndreaLigios, так з ними ви можете підвищити продуктивність в 100-1000 разів порівняно зі старою реалізацією
додано Автор AlexWien, джерело
+1, ці структури досить круті
додано Автор Andrea Ligios, джерело

You could use a Map to store your data (you have to write the Pair class). If you need to iterate the data in some specific order, make Pair Comparable, and use NavigableMap

4
додано
Отже, якщо я хотів би пройти через кожну точку на карті, не перевіряючи кожне можливе відображення, я міг би скористатися функцією TreeMap.keySet (), щоб отримати набір всіх ключових значень, а потім пройти через них?
додано Автор Reed B, джерело
+1 гарне рішення; бити мені це :) Я також люблю згадування про NavigableMap .
додано Автор Vivin Paliath, джерело
@KirilRaychev Я повторно реалізував точка для використання в emebedded системах, де java.awt не був доступний, це більше роботи, ніж спочатку.
додано Автор AlexWien, джерело
@Кирил Райчев: Добре пояснення.
додано Автор splungebob, джерело
Чому б не використовувати клас Point ?
додано Автор splungebob, джерело
@splungebob ви маєте на увазі java.awt.Point ? Я думаю, що завжди є поганою ідеєю використовувати класи, призначені для цілком інших цілей, просто тому, що вони мають власні властивості. Точка awt змінюється, може бути встановлена ​​удвоє, і може застосовуватися перетворення - абсолютно не те, що нам потрібно тут.
додано Автор jmruc, джерело
@ReedB так ви можете. Рекомендованим способом є ітерація entrySet , а не keySet , оскільки вона є більш ефективною, але вона буде виконана.
додано Автор jmruc, джерело

One approach could be Map>. The key on the outer map is the row value, and the key in the inner map is the column value. The value associated with that inner map (of type Data in this case) corresponds to the data at (row, column). Of course, this won't help if you're looking at trying to do matrix operations or such. For that you'll need sparse matrices.

Another approach is to represent the row and column as a Coordinate class or a Point class. You will need to implement equals and hashCode (should be very trivial). Then, you can represent your data as Map or Map.

2
додано

Ви можете мати список списків об'єкта, і цей об'єкт може кодувати його горизонтальне та вертикальне положення.

class MyClass
{
    int x;
    int y;
    ...
}
1
додано
Але тоді кожен раз, коли додається новий об'єкт, тому що я хочу мати унікальний набір балів, мені доведеться шукати список всіх даних, щоб побачити, чи це вже існує, перед тим, як оновити точку даних або додати новий. Я намагався уникнути цього неефективного процесу.
додано Автор Reed B, джерело
@ReedB це не мало недоцільності, особливо якщо у вас є список списків з зовнішнім списком, що відповідає x , а внутрішній список, що відповідає y . пошук буде O (x + y) складністю часу
додано Автор Sam I am, джерело

Моєю пропозицією для вас є використання Commons Math: бібліотека математики Apache Commons . Тому що це врятує ваш день, використовуючи силу математики, яку вимагає ваша програма.

0
додано

Я думаю, ви на правильному шляху, щоб зробити це в пам'яті ефективним способом - його можна легко реалізувати, використовуючи карту карт, загорнуту в клас, щоб дати чистий інтерфейс для пошуку.

Альтернативою (і більш ефективним способом використання пам'яті) буде використання єдиної карти, де ключ був кортеж (x, y). Однак це було б менш зручно, якщо вам потрібно зробити такі запити, як "дати мені всі значення, де x == деяке значення ".

0
додано
Карта карт виглядає багатообіцяючою. Як я вже сказав у пари інших коментарів, якщо я використовував окрему карту, яка була TreeMap, тоді слід було б порівняти вузли на основі певного хеш-значення, створеного з двох точок, як-от моя оригінальна ідея єдиного BST . Якщо ця Карта була лінійною картою, як і список, то це було б дуже неефективним, оскільки кожного разу, коли я хотів би додати дані, мені доведеться шукати лінійно через список, щоб побачити, чи він вже існує, перед тим, як оновити його або додати нова точка даних
додано Автор Reed B, джерело

Можливо, вам слід подивитися на FlexCompColMatrix, CompColMatrix та інші реляційні матриці з проекту Matrix toolkit .

Продуктивність дійсно залежить від співвідношення запису/читання та щільності матриці, але якщо ви використовуєте матричний пакет, це буде легше експериментувати, перемикаючи реалізацію

0
додано

Може бути, я тут надто спрощений, але я думаю, що ви можете просто використовувати звичайний HashMap . Він міститиме спеціальні об'єкти Point як ключі:

class Point {
    int x;
    int y;
}

Потім ви перевизначаєте метод рівності (і, отже, метод hashCode) на основі x і y . Таким чином, ви можете зберігати лише точки, які мають певні дані.

0
додано
Див. Редагування про хешпапках.
додано Автор Reed B, джерело
ІТ КПІ - Java
ІТ КПІ - Java
436 учасників