2D деректерін сақтау үшін деректер құрылымы идеясы?

Менде үлкен 2D торы бар, x-by-y. Қолданбаның пайдаланушысы осы тордағы нақты нүктелер туралы деректерді қосады. Өкінішке орай, тор үлкен 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 ішкі мәндерін олардың x мәндері негізінде салыстырады. Ішкі BSTs ұпайларды y мәндерімен салыстырады (және олардың барлығы бірдей). Сондықтан, бағдарламашы (5,6) тармағының бар-жоғын білгісі келсе, олар сыртқы BST-ті 5-ке сұрайды. Егер ішкі BST сол кезде бар болса, онда бағдарламашы ішкі BST-ге 6 сұрайды. қайтарылады.

Сіз мұны жүзеге асырудың жақсы әдісін ойлайсыз ба?

Өңдеу: HashMaps бойынша: Көптеген HashMaps іздеуге арналған массив болуы қажет. Біреуі «деректер [hash (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, көзі
Сіз өз операцияларын түсіндірмейінше, ең жақсы құрылымды табу мүмкін емес. Сондай-ақ, morton индекстелген массивтері бар нүктелермен бірге b-tree мүмкін. немесе hashmaps торы
қосылды автор AlexWien, көзі
Жақсы, бұл картаңыз пайдалану үшін жақсы. Бірақ сіз жылдамдықты кеңістіктегі проблемалық шешімдерді енгізген кезде, HashMap-ді Object негізделмеген, ол 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-ағаш .

Үлкен торап массивіне индексті кеңістіктік құрылымдардың біріне сақтаңыз. Мұндай кеңістіктік құрылымдар, егер деректер тең бөлінбеген болса, географиялық деректер сияқты қалаларда шоғырланған және теңізде ешқандай нүкте жоқ.

Ұзақ торды ұмытып, төртбұрышты ағашпен бірге қалу туралы ойланыңыз (Ойланыңыз, неге сізге жүйелі тор қажет? Тұрақты тор әдетте жеңілдетеді)

Нүктелерді сақтау үшін Объектілерді ешқашан пайдаланбаңыз. Мұндай нысанды объект болып табылатындығына байланысты 20 байт қажет! Үлкен деректер жиынтығы үшін жаман идея.

int x [] және int [] y немесе int [] xy массиві еске қолдануға өте ыңғайлы.

Оқуды қарастырайық

Ханан Саметтің «Көп өлшемді деректер құрылымдарының негіздері»

(Кем дегенде Кіріспе).

5
қосылды
Бұл жақсы құрылымдар, бірақ Quadtree жақсы болмайды, өйткені менің деректерім дискретті жолдар мен бағандарда, 2-ші тұрақты доменде бөлінген нүктелердің орнына төртбұрышты жобаланған. Жауап үшін рақмет!
қосылды автор Reed B, көзі
Quadtree тұрақты координат үшін арналған notz болды. Бұл бүтін координаттар үшін, әдетте екеуінің күші. Осылайша дискретті. Төртінші ағаш - сақтау орны емес, индекс. Жақын жерде ұпайларды табу үшін көп күш жұмсады. Сізге деректерді пинт ретінде (жол, кол) немесе (x, у) ретінде сақтауға болады. - Сіздің деректеріңіз біршама бөлінген немесе кейбір жерлерде кластерленген бе?
қосылды автор 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 Мен java.awt қолжетімсіз болатын жүйелерде қолдануға арналған Point-ты қайта жасадым, бұл бірінші кезекте тұрғаннан гөрі көп жұмыс.
қосылды автор AlexWien, көзі
@KirilRaychev: Жақсы түсініктеме.
қосылды автор 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 Mathematics Library . Өйткені ол сіздің күніңізді сақтап қалады, себебі сіздің қолдануыңыз қажет математикалық күшін пайдалану.

0
қосылды

Менің ойымша, сіз мұны дұрыс жолмен жасай аласыз, оны тиімді түрде жасауға болады - оны іздеу үшін таза интерфейс беру үшін сыныпқа оралған карталар картасын пайдалану арқылы өте оңай іске асыруға болады.

Баламалы (және одан да көп еске түсіруге арналған) көзқарас бір кнопкаға (x, у) арналған бірыңғай картаны пайдалану еді. Дегенмен, егер сізде x == some value 'деген барлық мәндерді беру сияқты сұрауларды жасау қажет болса, бұл ыңғайлы болады.

0
қосылды
Карталар картасы перспективалы болып көрінеді. Басқа да түсініктемелерде айтқанымдай, TreeMap-тің бір картасын пайдаланған болсам, онда екі нүктеден жасалған қандай да бір құнды мәнге негізделген түйіндерді салыстыруға тура келеді, мысалы, бірыңғай BST туралы түпнұсқа идеям сияқты . Егер бұл карта тізім сияқты сызықтық карточка болған болса, онда бұл өте тиімді болмайды, себебі деректерді қосқым келген сайын, ол оны жаңартып немесе жаңартпастан бұрын бар екендігін көру үшін тізім арқылы сызықты іздеуге тура келеді жаңа деректер нүктесі.
қосылды автор Reed B, көзі

Matrix құралы жобасы ішінен FlexCompColMatrix, CompColMatrix және басқа да сирек матрицаның іске асырылуын қарағыңыз келуі мүмкін. .

Шын мәнінде, жазу/оқу коэффициентіне және матрицаның тығыздығына байланысты болады, бірақ егер сіз матрицалық пакетті пайдалансаңыз, оны іске қосу арқылы эксперимент жасауға оңай болады

0
қосылды

Мүмкін, мұнда өте қарапайым, бірақ жай ғана HashMap қолдануға болады деп ойлаймын. Кілт ретінде Point нысандарын қолдануға болады:

class Point {
    int x;
    int y;
}

Содан кейін, сіз x және y негізделетін тең әдісті (және осылайша hashCode әдісі) басады. Осылайша, кейбір деректерді ғана сақтай аласыз.

0
қосылды
Hashmap туралы редакцияны қараңыз.
қосылды автор Reed B, көзі