Binární hledání – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama

Binární hledání – C / C++ – Fórum – Programujte.comBinární hledání – C / C++ – Fórum – Programujte.com

 
Hledat
Moderní platforma pro vytvoření vašeho nového webu – Wix.com.
Nyní už můžete mít web zdarma.
Vybavení pro Laser Game
Spuštěn Filmový magazín
Laser Game Brno

Toto vlákno bylo označeno za vyřešené.
Spuštěný nový filmový web Filmožrouti.cz — vše o Avengers, Pacific Rim, Thor, Star Wars…
Kevil0
Návštěvník
2. 9. 2018   #1
-
0
-

Jak upravit následující program, aby mi vrátil hodnotu indexu pole po zadání hodnoty = 7, která není v seznamu ? Jde mi vrácení nejvyšší hodnoty indexu pro zadanou hodnotu, kde je hodnota daného čísla v seznamu <= zadané hodnotě. Tj. pro hodnotu = 7 by měl program vrátit index 5 a pro hodnotu = 8 index 8. Data v seznamu jsou setříděna.

#include "pch.h"
#include <iostream>

int seznam[10]{0, 2, 3, 5, 5, 6, 8, 8, 8, 9};
int arr_size = sizeof(seznam) / sizeof(seznam[0]);


int main()
{
	for (int i = 0; i <= arr_size; i++)
	{
		printf("%i\n", seznam[i]);
	}
	printf("\n");

	int vlevo = 0;
	int vpravo = arr_size - 1;
	int stred = 0; 
	int hodnota = 3 ;
	bool nasel = false;

	//* Hledámě hodnotu v setříděném poli
	while (vlevo <= vpravo) {
		stred = (vpravo + vlevo) / 2;
		if (seznam[stred] == hodnota) {
			nasel = true;
			printf("%i\n", stred);
		}
		if (hodnota < seznam[stred]) {
			vpravo = stred - 1;
		}
		else {
 			vlevo = stred + 1;
		}
	}
}
Nahlásit jako SPAM
IP: 89.177.163.–
Jerry
~ Anonymní uživatel
214 příspěvků
3. 9. 2018   #2
-
0
-

#1 Kevil
přiznám se že nechápu zadání. když cheš vrátit hodnotu indexu pro hodnotu v poli tak na to ti stačí jden cyklus for a navíc pro hodnotu v poli 8  by ti to mělo vrátit index 6 při prohledávání zleva. Indexy se počítají od nuly. Je v tom nějakej chaos ...

Nahlásit jako SPAM
IP: 2a00:1028:83be:235a:84cc:d742:6bc4:9fda...–
gna
~ Anonymní uživatel
698 příspěvků
3. 9. 2018   #3
-
0
-

To se dělá hledáním prvního většího. Před ním pak je poslední menší nebo rovno.

std::upper_bound

Nahlásit jako SPAM
IP: 213.211.51.–
Kevil0
Návštěvník
3. 9. 2018   #4
-
0
-

#2 Jerry
On by se ten cyklus ale opakoval 35 milionkrát, tolik mám řádků ;-). Chaos v tom žádný není. Index 8ček je věcí, zda brát první 8ku zlava nebo zprava.

Nahlásit jako SPAM
IP: 89.177.163.–
Kevil0
Návštěvník
3. 9. 2018   #5
-
0
-

#3 gna
Takováto rada mi moc nepomůže. Už mi to ale funguje (najde index první hodnoty z více stejných hodnot zleva).
 

#include "pch.h"
#include <iostream>

int seznam[10]{0, 2, 3, 5, 5, 6, 8, 8, 8, 9};
int arr_size = sizeof(seznam) / sizeof(seznam[0]);


int main()
{
	for (int i = 0; i <= arr_size; i++)
	{
		printf("%i\n", seznam[i]);
	}
	printf("\n");

	int vlevo = 0;
	int vpravo = arr_size - 1;
	int stred = 0; 
	int hodnota = 8 ;
	bool nasel = false;
	int x = 0;
	int pozice = 0;
	
	

	//* Hledámě hodnotu v setříděném poli
 	while (vlevo <= vpravo) {
		stred = (vlevo + vpravo) / 2;
		if (seznam[stred] <= hodnota) {
			x = seznam[stred];
			pozice = stred;
		}
		if (hodnota > seznam[stred]) {
			vlevo = stred + 1;
		}
		else {
  			vpravo = stred - 1;
		}
	}
	printf("Nasel jsem %i na pozici %i\n", x, pozice);

}
Nahlásit jako SPAM
IP: 89.177.163.–
gna
~ Anonymní uživatel
698 příspěvků
4. 9. 2018   #6
-
0
-

Jo, už to funguje, jen to dělá něco jiného a řešení toho, na co ses ptal ti nepomůže.

Začínám si zvykat.

Nahlásit jako SPAM
IP: 213.211.51.–
Jerry
~ Anonymní uživatel
214 příspěvků
4. 9. 2018   #7
-
0
-

#5 Kevil
to asi hledáš nějakou hodnotu pulenim intervalu co ? no to je hezké, ale pomocí tohohle by ti to šlo rychlejc

https://cs.wikipedia.org/wiki/Fibonacciho_posloupnost

je to matematicky prokázaný :)

Nahlásit jako SPAM
IP: 2a00:1028:83be:235a:4981:87d9:7aa8:fffb...–
Kevil0
Návštěvník
4. 9. 2018   #8
-
0
-

#7 Jerry
Není mi jasné, k čemu bych měl Fibonacciho čísla použít. Pracuji s GPS souřadnicemi. Hledání čísel půlením intervalu je v sestříděném vektoru o 35 mil. čísel otázkou max. 25x porovnání (log 35 mil. / log 2). Dosud jsem (nesetříděná) čísla hledat ve dvou vnořených cyklech, které jsem procházel 2x 35 milionkrát. I tak to bylo v assembleru prakticky na stisk tlačítka. Půlením intervalu to nyní bude ihned. Potřebuji to pro real time vynášení tras pohybu bójí v moři volbou oblasti pohybem myši na obrazovce.

Nahlásit jako SPAM
IP: 89.177.163.–
Kevil0
Návštěvník
4. 9. 2018   #9
-
0
-

#6 gna
Program dělá přesně to, co jsem chtěl. Najde první nejbližší nižší nebo stejnou zadanou hodnotu čísla vektoru (index) zleva. Jde o celá čísla.

Nahlásit jako SPAM
IP: 89.177.163.–
Jerry
~ Anonymní uživatel
214 příspěvků
5. 9. 2018   #10
-
0
-

#9 Kevil
ty používáš takové záhadné algoritmy :) mám pocit že ten tvuj algoritmus se řešil už na zive.cz a tady taky ... no duležitý je že ti to funguje ok ... jo a zkusil si někdy vyjádření pozic ve sférických souřadnicích ? že ono totiž pak nemusíš takovýhle šílený prohledávání 35 mil. bodů dělat  ... mám totiž pocit že ten algoritmus smolíš už tak dva tři roky :) 

Nahlásit jako SPAM
IP: 2a00:1028:83be:235a:3957:ba32:7be9:270f...–
Kevil0
Návštěvník
5. 9. 2018   #11
-
0
-

#10 Jerry
Na to, že se programováním vůbec neživím mi nepřipadá nějaký extrém se naučit základy C++ za cca 3 měsíce pro relativně náročný úkol. Program dělá to co potřebuji, jen se ho teď snažím urychlit. Oceňuji, že mi pomohly i některé rady zde ve fóru :-).

U GPS mi stačí x, y. Sférické souřadnice nepotřebuji.

Nahlásit jako SPAM
IP: 89.177.163.–
MilanL+1
Věrný člen
5. 9. 2018   #12
-
0
-

#8 Kevil
to ještě jde, v podstatě při dnešní rychlosti cpu je to otázka µs (než pustí tlačítko myši mělo by být hotovo), pokud by ta velikost seznamu byla o víc než řád větší uvažoval bych po setřídění o indexaci rozsahů.

Nezapomeň si ošetřit stejné hodnoty, pokud je víc hodnot tak tím programem můžeš narazit na to, že ti pozice bude ukazovat na jinou než 1. nalezenou.

u toho výpočtu s /2 bych použil bud DIV nebo bitový posun.

Nahlásit jako SPAM
IP: 91.139.9.–
MilanL+1
Věrný člen
5. 9. 2018   #13
-
0
-

hele trošku jsem si s tím hrál optimalizoval bych takto

první podmínku lze vynechat

X ve smyčce je zbytečné stačí až po smyčce x=seznam[pozice]

a pozice = stred; hodit do ELSE té druhé podmínky, jen vzhledem k tomu že, když tam to číslo není to ukáže na první vyšší, pořešit za smyčkou

if (seznam[pozice]<> hodnota) then pozice -= 1;

X ve smyčce je zbytečné stačí až po smyčce x=seznam[pozice]

Nahlásit jako SPAM
IP: 91.139.9.–
MilanL+1
Věrný člen
5. 9. 2018   #14
-
0
-

#13 MilanL
ještě tam pořešit v

if (seznam[pozice]<> hodnota) then pozice -= 1;

situaci, kdy je hledaná hodnota menší než nejmenší hodnota v poli, kdy se vrátí pozice 0 a není rovná hodnotě, tzn přidat do podmínky "and (pozice>0)" , aby se pozice nedostala do -

Nahlásit jako SPAM
IP: 185.112.167.–
Kevil0
Návštěvník
5. 9. 2018   #15
-
0
-

#14 MilanL
Dostal jsem tip, jak to správně udělat:

#include <iostream>
#include <algorithm>
 
int main() {
    int arr[] = {0, 2, 3, 5, 5, 6, 8, 8, 8, 9};
    auto beg = std::begin(arr);
    auto it = std::upper_bound( beg, std::end(arr), 8 );
    if( it == beg ) {
        std::cout << "no value less than 8 found" << std::endl;
        return 0;
    }
    std::cout << "index is " << std::distance( beg, it ) - 1 << std::endl;
    return 0;
}

Funguje to. Rád bych to naprogramoval v assembleru, kde nemohu použít speciální direktivy jako "upper_bound". Viz popis https://en.cppreference.com/w/cpp/algorithm/upper_bound

Nahlásit jako SPAM
IP: 89.177.163.–
Kevil0
Návštěvník
6. 9. 2018   #16
-
0
-

Pro ošetření výskytu více stejných hodnat za sebou a nastavení indexu na poslední z nich zprava stačilo na konec programu půlení v assembleru přidat:

    mov rax, r13          ; V r13 nalezený řádek (index) zleva
    inc rax
    call Get_IND_Value    ; Vrátí hodnotu na řádku do r15d
    cmp edx, r15d         ; Hodnota řádek + 1 je stejná ?
    ja Najdi_K            ; Ne
        inc r13           ; Ano, řádek = řádek + 1
        jmp Najdi_E
    Najdi_K:
Nahlásit jako SPAM
IP: 89.177.163.–
MilanL+1
Věrný člen
6. 9. 2018   #17
-
0
-

#16 Kevil
no pro hledání posledního výskytu stačí drobet upravit to chování podmínky v tom tvým C programu a prohodit ty řádky vpravo= vlevo= ,nebo hledat hodnotu +1 a vrácenou pozici snížit na předchozí, to by mělo vrátit poslední výskyt hodnoty nebo poslední nižší.

Co se týče assembleru záleží z jakého pole hledáš, jestli z pole celých záznamů nebo jen z pole souřadnic.

Já bych to řešil drobátko jinak, udělal bych si pro každou souřadnici převodní setříděné pole 2x DWORD/INT (souřadnice, index řádky) kvůli počítání ofsetů v asm pak:

registry:

- Začátek prohledávání - třeba RSI
- Hodnota - např. EDX (32bit integer)
- Size (COUNTer) - ECX

- pozice některý další registr výchozí = 0

Hledání:

pak ti stačí rozpůlit Size (posunem doprava o 1)

pokud size = 0 konec (použít asi CMP nebo AND nebo OR) aby se nezměnilo

porovnat [Začátek+Size*8] s hodnotou

pokud je hodnota větší přičíst k Pozici Size+1, a k Začátku (Size+1)*8

opakovat hledání

konec: (size/2=0)

Začátek ukazuje na adresu s hodnotou nebo většího souseda.

Snad tam není žádná větší chyba.

EDT:  na konci snad ještě ošetřit, zda jsi se nedostal  mimo pole pokud je hodnota větší než největší hodnota v poli, případně by se tohle dalo ošetřit před vstupem do hledání, hledat jen, když je hodnota v rozsahu pole, tzn >pole[0] a <pole[size-1] 

Nahlásit jako SPAM
IP: 91.139.9.–
Kevil0
Návštěvník
6. 9. 2018   #18
-
0
-

#17 MilanL
Takhle nějak to dělám ;-). Originální data jsou v textovém souboru s pevnou délkou sloupců. Souřadnice ve tvaru XXX,xxx převedu na DWORD vynásobením 1 000 a u záporné LAT přičtu 90 000 abych neřešil int se znaménkem, LON hodnoty jsou v rozsahu 0-360°. Za DWORD hodnotami LAT/LON mám pak další DWORD které nepřímo odkazují na řádek s hodnotou LAT/LON po setřídění. Řádek je dlouhý 125  bytů, na začátku ponechám v ASCII č. bóje a LAT/LON, tyto hodnoty mám pak uloženy v DWORD od pozice 56 (kde jsou v ASCI další údaje, které nepotřebuji). Hledám tedy v setříděné tabulce. Vlastní funkce pro hledání půlením intervalu pak reálně vypadá takto:

Najdi:											; r11=L, r12=P, r13=S, r14=pro porovnání, r15=hodnota,rcx=125, rbx=pozice; použit rax a rdx
mov r14, rax									; Hodnota pro porovnání
xor r11, r11									; L (příprava)
mov r12, 35702066								; řádků
dec r12											; pravý okraj pole menší o jedničku
mov rcx, 125									; Konstanta pro násobení
Najdi_W:
	mov rax, r11
	cmp rax, r12								; L <= P ?
	ja Najdi_E								    ; Ne, tj. konec
	add rax, r12
	shr rax, 1
	mov r13, rax								; r13=L+P/2
	imul ecx									; edx:eax = eax * ecx
	shl rdx, 32
	or rax, rdx									; sloučíme Hi edx a Lo eax
	add rax, rbx								; Přičteme pozici
	mov edx, [rsi+rax+4]					    ; Vyvedneme č. řádku s odkazem na IND hodnotu LAT/LON
	mov eax, edx
	imul ecx									; edx:eax = eax * ecx
	shl rdx, 32
	or rax, rdx									; sloučíme Hi edx a Lo eax
	add rax, rbx								; Přičteme pozici
	mov edx, [rsi+rax]					        ; IND hodnota LAT/LON
	cmp edx, r14d								; [stred] <= hodnota ?
	ja Najdi_D
	mov r15d, edx								; Nalezená hodnota	
Najdi_D:
	cmp r14d, edx								; hodnota > [stred]
	ja Najdi_P									; Ano
	mov r12, r13
	dec r12
	jmp Najdi_W
Najdi_P:
	mov r11, r13
	inc r11
	jmp Najdi_W
Najdi_E:
mov rax, r13
inc rax
call Get_IND_Value
cmp edx, r15d									; Hodnota řádek + 1 je stejná ?
ja Najdi_K										; Ne
	inc r13										; Ano, řádek = řádek + 1
	jmp Najdi_E
Najdi_K:
ret
Nahlásit jako SPAM
IP: 89.177.163.–
MilanL+1
Věrný člen
6. 9. 2018   #19
-
0
-

#18 Kevil

no nevím jak často se mění ten textový soubor, já bych si to snažil zjednodušit

přemejšlel bych nad 
- buď jednorázovým převodem na binárku s přidáváním nových řádek, když bude třeba.,

- nebo bych zkusil upravit velikost řádky na 128, nemusíš pak na ten ofset používat násobení, ale několika násobně rychlejší posun (offset = index shl 7) a to samé index z ofsetu (index = offset shr 7)

co se týče toho filtrování tam bys musel pracovat se zužováním oblastí nebo subtříděním

subtřídění:

výchozí setřídění Lon

vyhledej indexy LONmin a LONmax (uložit je nutno vrátit třídění, nebo použít kopii)

setřiď úsek mezi nimi podle LAT

vyhledej indexy LATmin LATmax 

výsledný úsek obsahuje pole v rámci oblasti

případné setřídění zpět podle LON

Zužování:

setřídění podle klíče LON:LAT

hledej LONMIN

hledej následující vyšší

v úseku najdi LATmin a LATmax 

oblast přenes do výsledku

následující vyšší do LONMIN

je li nižší než LONmax opakuj od hledej následující vyšší

* vzhledem k rozsahu čísel, bych použil volné bity v LON LAT k zakodování čísla řádky

další možnosti rozdělit si mapu na sektory a předhledat do sektorů a hledáním řešit menší oblasti případně přesahy

Nahlásit jako SPAM
IP: 91.139.9.–
MilanL+1
Věrný člen
6. 9. 2018   #20
-
0
-

#19 MilanL
Když použiješ větší strukturu pole LON LAT BOJE Řádek můžeš. pak výsledek snadno přenést do toho výsledného pole pro vykreslení, řešíš nějak když bóje opustí oblast a zas se do ní vrátí?

Nahlásit jako SPAM
IP: 91.139.9.–
Kevil0
Návštěvník
6. 9. 2018   #21
-
0
-

#20 MilanL
Program hledá čísla bójí, které se pohybovaly ve dvou čtvercových oblastech podle zadaných LAT/LON. Nevadí, že nějaká bóje oblast opustí a pak se do ní vrátí. Ve finále pak vynáším celou trasu bojí, které jsem našel (t.j. trasa dané bóje prošla oblastí 1 a 2). Při kreslení musím ještě přepočítat souřadnice na body na obrazovce a uložit trasu do pomocného vektoru pro funkci Polyline(hdc, *apt, cpt), to už dělám v C++.

Na třídění (soubor si pak uložím a nemusím data pokaždé třídit) používám Merge Sort. Celočíselné násobení 125 je velmi rychlé, vynásobení rcx 125 za pomoci násobků 2, posunů a sčítání je pomalejší:

	mov rax, rcx
	shl rcx, 2		; *4
	add rax, rcx
	shl rcx, 1		; *8
	add rax, rcx
	shl rcx, 1		; *16
	add rax, rcx
	shl rcx, 1		; *32
	add rax, rcx
	shl rcx, 1		; *64
	add rax, rcx
Nahlásit jako SPAM
IP: 89.177.163.–
MilanL+1
Věrný člen
6. 9. 2018   #22
-
0
-

k tomu násobení jsem, ale psal, zarovnat si tu délku řádky na 128 (v rámci těch 35M řádek 115MB navíc), pak je to 1 rotace, minimálně 5x spíš víc rychlejší než IMUL

Nahlásit jako SPAM
IP: 91.139.9.–
Kevil0
Návštěvník
6. 9. 2018   #23
-
0
-

#22 MilanL
Jasně vím o tom. To násobení má minimální vliv na celý program. Musím ještě upravit hledání ve druhé oblasti půlením a dám pak vědět, jak to běhá.

Nahlásit jako SPAM
IP: 89.177.163.–
gna
~ Anonymní uživatel
698 příspěvků
6. 9. 2018   #24
-
0
-

Postřehli jste, že v tom odkazu je i implementace? Prostě není co řešit.

Nahlásit jako SPAM
IP: 213.211.51.–
MilanL+1
Věrný člen
6. 9. 2018   #25
-
0
-

#24 gna
to ano, pro jednoduché typy, on chce hledat ve struktuře a pokaždé podle jiného prvku, implementaci by si musel upravit pro konkrétní strukturu.

Nahlásit jako SPAM
IP: 185.112.167.–
MilanL+1
Věrný člen
6. 9. 2018   #26
-
0
-

hele, můj názor, pokud to chceš opravdu urychlit, zapoměl bych na textová data, pokud kromě čísla boje a souřadnic nic dalšího nepotřebuješ a to pro to hledání a vykreslení trasy fakt nepotřebuješ, tedy kromě ještě indexu řádky.

4x dword IDboje, LON, LAT, řádka

adresování při prohledávání [RSI + index*16 + pozice čísla(0=boje, 4=Lon, 8=LAT, 12=řádka)]

a žádný další složitý výpočty okolo, potřeba paměti cca 600MB.

o vláknech neuvažuješ? nemyslím pro hledání, ikdyž i tam by byla možnost např prohledávání obou oblastí a pak sjednocení výsledku,

1. vlákno hledání

  -  výstup: pole nalezených bojí v oblastech + counter + semafor konce

2. vlákno převodu na souřadnice pro boji

  -  vstupem výstupy z 1. vlákna

  -  výstup data pro vykreslení pro jednotlivé boje + counter (když je boje komplet) + konec

3. vlakno obsluha polyline

  - vstupem výstupy z 2.vlákna

Nahlásit jako SPAM
IP: 185.112.167.–
MilanL+1
Věrný člen
6. 9. 2018   #27
-
0
-

#26 MilanL
mám chut si to naprogramovat abych si některý ty algoritmy vyzkoušel na vlastní oči, asi tomu obětuju čas co budu mít o víkendu na brigádě - mám 3 noční a od cca 1/2 noci do rána je klid, akorát pojedu 32 bitově, nemám podporu 64b překladače a nechci se trápit s nějakým hledáním sa zprovoznováním ve VS2015 express.

Nahlásit jako SPAM
IP: 185.112.167.–
Kevil0
Návštěvník
6. 9. 2018   #28
-
0
-

#27 MilanL
Už ti nahrávám soubor 4 GB, se kterým pracuji. Za chvíli sem dám odkaz ke stažení a popíšu strukturu řádku, ať máš reálná data ;-).

Nahlásit jako SPAM
IP: 89.177.163.–
Kevil0
Návštěvník
6. 9. 2018   #29
-
0
-

Nesetříděný textový soubor s daty 4 GB je ke stažení na https://uloz.to/!mQDfiGbQdDlP/bda-180823-dat

Pevné pozice, šířka sloupců: 8, 5, 7, 5, 10, 10, 80. Počet řádků 35 702 066.

č. bóje (ID), měsíc, den a 1/4 dne (GPS pozice odesílány každých 6 hodin), rok, LAT, LON, nepotřebná data

Pro začátek lze najít 7 bójí (čísla znám), které prošly oblastí:

LATa1 = -5,9;
LATa2 = -6,6;
LONa1 = 104,8;
LONa2 = 106,6

Mohu také případně nahrát soubor s ASCII údaji převedenými na DWORD + DWORD s nepřímým odkazem na setříděné hodnoty LAT, LON a ID. Ponechal jsem v něm ale také původní ASCII hodnoty.
 

Nahlásit jako SPAM
IP: 89.177.163.–
MilanL+1
Věrný člen
6. 9. 2018   #30
-
0
-

#29 Kevil
proč jsi to nezkomprimoval? jsou to textová dat to bude mít v zipu tak 300-400M :) , no neva, už stahuju rychlost mám dobrou není problém

Ty řádky vím to jsem viděl v tom programu na hledání, jeden z registrů u kterých jsem pochopil význam :D

Nahlásit jako SPAM
IP: 185.112.167.–
Kevil0
Návštěvník
6. 9. 2018   #31
-
0
-

#30 MilanL
V zápalu boje mě to nenapadlo zkomprimovat... sorry.

Nahlásit jako SPAM
IP: 89.177.163.–
MilanL+1
Věrný člen
7. 9. 2018   #32
-
0
-

#31 Kevil
hele nedávno jsem viděl pěknej kod počítající v textu výskyt vybraných slov, k urychlení použil rozpůlení oblasti s využitím různých regostrů pro bazi a indexaci v jednom průběhu hledání by se tak daly najít 2 hodnoty, pokud se použije ta zjednodušená struktura.

Promýšlím různý varianty setřídění a hledání zatím mi nejlíp vychází asi primární setřídění LAT (menší rozsah) sekundární třídění 64bit idboje+LON

v první fázi vyhledat indexy první pro >= LATmin a poslední pro <=LATmax, to dá interval pro hledání LON

hledání LON hledaná hodnota 64bit idboje z prvího indexu pro hledání LON + LONmin

64bit hledání první >= 

porovnat s LONmax

když menší nebo rovno jen ulož id boje

v hledané hodnotě změň id boje na číslo nalezené boje + 1 a nastav počátek hledání na aktuální index+1 a konec na index nalezeného LATmax pokud je počátek menší než konec opakuj 64bit hledání >=

pro hledání oblasti 2 stejný postup , s malou změnou u hledání LON do hledaní doplňovat ID bojí nalezených v oblasti 1 a obousměrně kontrolovat

pokud při nalezení odpovídá ID boje, je boje v obou oblastech ulož a opakuj hledání pro další boji z oblasti1 (1)

 pokud ne porovnej s dalšími bojemi z oblasti 1 dokud je > v okamžiku když je = ulož a v obou případech <= opakuj pro další boji z oblasti1 (1) dokud, se nedostaneš na konec seznamu bojí z oblasti1,

(1) počátek aktuální pozice + 1, konec pozice nalezeného LATmax, respektive indexy

doufám, že to pochopíš, v podstatě jde o docela velké zjednodušení, hledání LATmin max vyžaduje obojí stejný počet kroků tak bych to dělal najednou jen se na start a counter použijou jiný registry.

jen až to budu zkoušet já budu muset jít přes 8-12bit indexy bojí a kombinaci s LON do 32 bitů

Nahlásit jako SPAM
IP: 185.112.167.–
Kevil0
Návštěvník
7. 9. 2018   #33
-
0
-
Nahlásit jako SPAM
IP: 89.177.163.–
MilanL+1
Věrný člen
7. 9. 2018   #34
-
0
-

#33 Kevil
kouknu na to a když tak zkusím. já mám 2015 kvůli podpoře XNA - jsem synovi kolegy z práce ladil a vychytával mouchy v menší hře co měl jako projekt do školy.

Jinak uvědomuješ si, že

Souřadnice ve tvaru XXX,xxx převedu na DWORD vynásobením 1 000 a u záporné LAT přičtu 90 000 abych neřešil int se znaménkem, 

to přičtení 90 000 jen k záporným Ti v tom udělá pěknej guláš?

Rozsah LAT je -90 .. 0 .. +90, když to přičteš jen k záporným zamíchají se záporné do kladných při tom hledání, jedině že bys někam schoval znaménko, ale to zas musíš brát v potaz v těch třídících a hledacích funkcích.

Lepšíí by bylo přičíst těch 90 000 ke všem LAT. pak budeš mít 0°=jižní Pól, 90 000 rovník 180 000 severní pól

Nahlásit jako SPAM
IP: 91.139.9.–
Jerry
~ Anonymní uživatel
214 příspěvků
7. 9. 2018   #35
-
0
-

#34 Kevil
díval jsem se na ten tvuj textový soubor BDA_180823.dat a ty teda prohledáváš tento textový soubor jo ? No to je docela zajímavý, takže ho celej načteš do paměti ???? a pak v něm hledáš ??? nebo jak to je ???

 7702986    3  8,000 1988    -1,320   274,848    25,473   999,999   999,999   999,999  0,25315E-04  0,33929E-04  0,45179E-02

Nahlásit jako SPAM
IP: 2a00:1028:83be:235a:c0cf:f9bb:4ace:daaa...–
MilanL+1
Věrný člen
7. 9. 2018   #36
-
0
-

#35 Jerry

čísla bojí a souřadnice si převádí na DWORDy

podle mě je to kontraproduktivní dala by se z toho udělat taková nádherná strutura

Nahlásit jako SPAM
IP: 193.165.115.–
MilanL+1
Věrný člen
7. 9. 2018   #37
-
0
-

#29 Kevil

podle toho jak jsi popsal tu trukturu tak: ?

číslo bóje MM DD+1/4 RR . . .LAT . . . LON . .  tady začíná smetí?
 7702986    3  8,000 1988    -1,320   274,848    25,473

není mezi rokem a LAT ještě něco třeba výška?
Nahlásit jako SPAM
IP: 193.165.115.–
Kevil0
Návštěvník
7. 9. 2018   #38
-
0
-

#37 MilanL
Data jsem stáhl ze stránky http://www.aoml.noaa.gov/phod/gdp/index.php. Ty čtyři soubory *dat.gz jsem sloučil do jednoho a nahradil desetinné tečky čárkou. Na stránce ftp://ftp.aoml.noaa.gov/phod/pub/buoydata/ je jejich popis včetně struktury, soubor "header_buoydata.txt".

Když budeš potřebovat, mohu ti poslat odkaz na setříděný soubor podle LAT, LON, ID a data/času. Soubor je stejný, jako ten co máš, jen jsem na nevyužitá místo v řádku uložil DWORD hodnoty LAT, LON... a DWORD odkaz na řádek kde lze pomocí nepřímého odkazu přečíst setříděnou hodnotu. Příklad: na prvním (nultém) řádku setříděného souboru najdeš na pozicích 56 DWORD LAT (hodnota ASCII ze začátku řádku) a hned za ní, pozice 60 DWORD odkaz na řádek, kde je nejnižší hodnota LAT, vynásobením tohoto čísla 125 dostaneš č. řádku s nejnižší hodnotou LAT na pozici 56 DWORD.  Odkaz na další stejnou nebo vyšší hodnotu LAT je pak na dalším řádku atd. Dtto pro LON (64 + index 68), ID (72 + 76) a Datum/čas (80 + 84). Datum čas jsem převedl do DWORD na počet bitů 11+4+5+2 t.j. rok, měsíc, den a 1/4 dne. Tj. 7.9.2018 + 3*6 hodin je ve tvaru 0x3F149F.

Nahlásit jako SPAM
IP: 89.177.163.–
Kevil0
Návštěvník
7. 9. 2018   #39
-
0
-

#35 Jerry
Se souborem se nemazlím. Na 1,5x ho celý načtu naráz (po 2 501 566 399 bytech) do alokované paměti 5 GB (VirtualAlloc) a pak s ním pracuji ;-).

Nahlásit jako SPAM
IP: 89.177.163.–
Jerry
~ Anonymní uživatel
214 příspěvků
8. 9. 2018   #40
-
0
-

#39 Kevil
aha takže ten 4GB soubor dat co načteš do paměti necháš jak je a prohledáváš ho půlenim intervalu jo ? nebo ho nějak ještě třídíš ? Já že ty položky LAT:-1,320  LON:274,848  , kde LAT násobíš 1000 a přičteš 90000 sou na 3 desetinný místa a LAT je v rozsahu +/-90° a LON je v rozsahu 0..360°... a pak to asi třídíš že ? 

.... přiznám se že nějak nechápu proč to všechno děláš ? tak LAT máš v originále v rozsahu -90,000 do +90,000 a předěláš to na rozsah +000000 do +180000 a LON máš v rozsahu +000,000 do +360,000 a předěláš ho na rozsah +000000 do +360000. ... hele s tim algoritmem se patláš už skoro rok ne ? 

...nechápu proč ty pole třídíš podle LAT nebo LON ... vždyť už ty data máš připravený ke zpracování formou LBA a prohledávání Fibonacciho algoritmem, když trváš na tom tvým "divným" způsobu zpracování. 

já osobně bych to dělal následovně: počet bójí v moři je cca +/- pevný a boje neustále vysílají data a to 4x denně takže záznamy ze souboru BDA_180823.dat bych při načítání do paměti roztřídil tak, že bych si vytvořil K struktur s názvem třeba Buoy_Item, kde každá struktura by odpovídala jedné boji a do této struktury bych nacpal data konkrétní údaje o poloze boje podle času do sekvenčního binárního stromu typu LIST<> a vše toto již při načítání do paměti. Ke struktuře LIST mužeš přistupovat i jako k poli pomocí indexu. Takže struktura by vypadala následovně:

ref class Positon_Item {

     Int32 LON;

     Int32 LAT;

     DateTime^ DateItem;

     constructor Positon_Item(){

           Int32=0;

           Int32=0;

          DateItem=Null;

     } // Positon_Item()

}// Positon_Item

ref class Buoy_Item {

     Int32 BuoyID ;

     List<Position_Item> PositionList^;

     constructor Buoy_Item(Int32 t_buoyID){

           PositionList<Position_Item^> = gcnew Position_Item<Position_Item^>();

           BuoyID=t_buoyID;

     } // Positon_Item()

     destructor Buoy_Item(){

          delete( PositionList ); 

     }// Buoy_Item

}// Buoy_Item

...tim by si měl data načtený do paměti a teď musíš vytvořit pole indexů LBA jako seznam LIST<> aby si mohl rychle najít boje, které jsou v určité oblasti, což uděláš současně při načítání dat do struktur Buoy_Item. Takže položka LBA_Item bude

ref class LBA_Item{

     UInt64 LBAItem;

     Buoy_Item^ buoyItemRef; 

} // LBA_Item   

a pak pochopitelně

LIST<LBA_Item^> LBAList = gcnew LIST<LBA_Item^>();

no a to je všechno. LBAItem bude vyjádřeno jako LBA=360000*LAT+LON, kde LAT je v rozsahu 0..179999 a LON v rozsahu 0..359999 a celkem je tedy k dispozici 180000x360000=64.800.000.000 bloků ve formě řídkého pole neboli řídké matice a protože to je struktura LIST mužeš k ní přistupovat s využitím indexu pole. Současně při načítání pole zatřiďuješ podle velikosti LBA nebo to mužeš setřídit až na konci načítání to je fuk. Nebo pole LBAList mužeš vytvořit rovnou jako k-tree strukturu kde k bude 2, což by bylo asi nejlepší. V tom případě bys se LBA_Item upravila na 

ref class LBA_Item{

     LBA_Item^ parentLink;

     LBA_Item^ leftLink;

     LBA_Item^ rightLink; 

     UInt64 LBAItem;

     Buoy_Item^ buoyItemRef; 

} // LBA_Item   

to by asi bylo nejlepší protože data pole LBAList neustále přibývají, když mám 10000 boji tak mi každej den přibude 40000 záznamů... t.j. 14,6 milionu ročně ... a přitom se předpokládá, že dvě a více bojí mohou mít stejné souřadnice což je pochopitelné 

ty samozřejmě všechno děláš v native C++ takže k-tree si asi uděláš sám .. 

taky by to šlo udělat tak, že si uděláš na disku soubor, jehož velikost je >64GB a každá položka ukazuje na soubor dat, ve kterém budou ID bojí, které bodem prošly :))) takže ten soubor bude mít 320GB a každá položka bude mít 5 bytů (40 bitů), což bude název souboru dat, ve kterém se nachází data boji které prošly daným bodem bomba ne ? :))) takže na serveru bude diskové pole cca 186GB dat (10000 boji x 4 záznamy deně x 356 dni x 100 let x 128 bytů na záznam ) takže jeden disk SSD 1TB ti vystačí v pohodě na 100 let ukládání dat :))) a načítání by probíhalo tak, že nastavíš seek na pevnou pozici v souboru 320GB přečteš bloky dat podle zvoleného obdélníku o rozměrech +/- LAT .. +/- LON a těch bloků dat bude podle LBA víc a pak načteš rovnou data z jednotlivých souborů pozic boji a hned je zobrazíš jako lomenou čáru protože je budeš mít setříděný podle času ...

no je to prostě hezký povídání ... :) 

Nahlásit jako SPAM
IP: 2a00:1028:83be:235a:49ff:c521:e1e3:8418...–
Kevil0
Návštěvník
8. 9. 2018   #41
-
0
-

#40 Jerry
Ano, postupuji přesně tak, jak jsi to popsal.

Amatérsky za zajímám o letecké katastrofy včetně záhady zmizení MH370. Mj. jsem v kontaktu s očitým svědkem pozorování hořícího "objektu" Mikem McKayem z Nového Zélandu. Po zadání souřadnic 6 nalezených trosek (vč. flaperonu na ostrově Reunion) a procházením Indického oceánu ve dvou vnořených cyklech po 1° od 0° do 40° S a od 80° do 108° E jsem pomocí programu zjistil jako nejpravděpodobnější místo původu nalezených trosek souřadnice 11° S a 84° E (v tomto čtverci jsem v součinu našel nejvíce bóji, kterou danou oblastí propluly a dostaly se do blízkosti míst nálezů všech trosek).  V cyklu 2x 35 mil. řádků trval výpočet jedné oblasti 1°x1° cca 2,5 sekundy. Půlením intervalu (25 porovnání) to bude určitě ihned. Jde o oblast rovníkových proudů, do které se podle mého názoru mohly trosky snadno dostat z pobřeží Vietnamu přes Sundskou úžinu mezi Sumatrou a Jávou. Let MH370 podle mě a podle všech dostupných informací havaroval v Jihočínském moři u pobřeží Vietnamu.

Dnes snad dokončím upravený program, který hledá data pomocí půlením intervalu, to již spolehlivě funguje. Nalezené bóje musím jen zkopírovat za sebe pro jejich předání C++, aby je vykreslil na mapě.

Někdo my také radil použít např. QGIS, grafický informační systém. Ten ale není stavěn na miliony řádků. I když jsem data převedl do tvaru jeho databáze, trvá pouhé otevření dat asi 10 minut… Dříve jsem používal Excel, kdy jsem textový soubor externě připojil pomocí PowerQuery v Excelu a zadáním podmínek hledání jsem dostal souřadnice do tabulky v Excelu. Jeden dotaz trval cca 3 minuty. Pak jsem souřadnice nalezených bójí převedl na jedné webové stránce z Excelu do KML a vynesl na Google Earth.

Přidávám ještě odkaz na převedená (DWORD) a setříděná data, popis pozic viz výše, v souboru je 22 797 bójí a má 35 702 067 řádků:
https://uloz.to/!XpZdcLPdtNC7/srt-180823-dat

A příklad výstupu mého programu (hledání), vynesení bójí ještě přes Excel a Google Earth:
https://image.ibb.co/f2mck9/MH370_6_1184.jpg

Nahlásit jako SPAM
IP: 89.177.163.–
MilanL+1
Věrný člen
8. 9. 2018   #42
-
0
-

#40 Jerry
no uvažoval jsem o něčem podobným, jako máš tu mapu LON x LAT jen hrubější rozlišení místo na 1/1000 stupně tak po větších kusech 1/10 /20 /50 /100, podle toho jakou by chtěl mít přesnost toho vyhledávání

Nahlásit jako SPAM
IP: 193.165.115.–
Kevil0
Návštěvník
8. 9. 2018   #43
-
0
-

#42 MilanL
To rozlišení mám na jeden celý stupeň. Samozřejmě beru v úvahu, že jsou výchozí souřadnice vynásobené 1 000 krát.

Nahlásit jako SPAM
IP: 89.177.163.–
Jerry
~ Anonymní uživatel
214 příspěvků
8. 9. 2018   #44
-
0
-

Kdyby sis udělal RAM disk z paměti grafický karty, třeba 2GB tak bys pak měl to prohledávání MNOHEM rychlejší  

https://www.softpedia.com/get/System/Hard-Disk-Utils/GPU-Ram-Drive.shtml

a pravdou je, že zobrazení 35.000.000 úseček v 3D enginu na grafický kartě je v podstatě real time a ořezávání je automatické, takže ... možná že by bylo jednoduchý řešení vytvořit si seznam úseček z bodů a ty prostě nasypat do VRAM grafický karty s ... řekněme 8GB RAM DDR5 no a když si zvolíš okno tak 3D engine za tebe udělá všechno víš :))) a nemusíš  používat to hrozný prohledávání stromů a pod. :))) možná ti to někdo měl říct než si s tim před rokem začal ...

Nahlásit jako SPAM
IP: 2a00:1028:83be:235a:c15a:aba7:fa7:30cd...–
Jerry
~ Anonymní uživatel
214 příspěvků
8. 9. 2018   #45
-
0
-

#44 Jerry
to zobrazení by pak bylo v pravoúhlý síti, nikoliv ve sférický, běžné graf. karty neumí zobrazovat sférické souřadnice, nicméně pokud by si netrval na zobrazování celé sféry jako "sféry" tak by si mohl přepočítat souřadnice LAT a LON na danou síť třeba na Robinsonovo zobrazení což by bylo rozumný.  Viz zde

https://is.mendelu.cz/eknihovna/opory/zobraz_cast.pl?cast=59996

takže princip zobrazení: uděláš úsečky, nasypeš je do grafický karty a vybereš okno a necháš zobrazit a nemusíš nic jinýho dělat žádný půlení intervalu a pod. kraviny 

Nahlásit jako SPAM
IP: 2a00:1028:83be:235a:c15a:aba7:fa7:30cd...–
MilanL+1
Věrný člen
8. 9. 2018   #46
-
0
-

#44 Jerry
no on chce zobrzovat jen to co odpovídá filtru

Nahlásit jako SPAM
IP: 193.165.115.–
MilanL+1
Věrný člen
8. 9. 2018   #47
-
+1
-
Zajímavé

#43 Kevil
při tak hrubém rozlišení bych udělal jednoduché 2D pole (při 1° je to 180x360=64,800, při 0,1° 6,48M) pointerů na seznamy bojí a počtu (může být případně na 1 místě v seznamu), které daným "čtvercem" prošli, vzhledem k tomu, že chceš jen info, Pak ti stačí projít dvouúrovňově to pole od LONmin-max a LATmin-max a pokud je pointer nenulový, načíst si boje samozřejmě řešit duplicity při více výskytech 1 boje v dané oblasti.

Nebo místo 2D pole udělat tu řídkou mapu, ale tam budeš muset vyhledaá interval vyších souřadnic a mezi nimi vyhledat tu nižší, každopádně na to hledání půlením stačí 8-9 cyklů.

Už na tom pracuju, zatím mám hotový načítání a pracuju na převodu, je blbost pracovat s tím textákem.

Nahlásit jako SPAM
IP: 193.165.115.–
Kevil0
Návštěvník
8. 9. 2018   #48
-
0
-

#47 MilanL
To, že ve čtverci 1°x1° hledám bóje, které jím prošly vůbec nesouvisí s nějakým "hrubým rozlišením". Jde prostě jen o to prohledal trasy bojí a vybrat z nich ty, které prošly daným čtvercem. Ve finále jsem pro 6 trosek našel ve čtverci 11° S 84° E nejvyšší součin (abych zřetelně viděl oblasti, kterými prošlo nejvíce bójí) počtu bójí = 1 600 (vyšší hodnotu u rovníku jsem nebral v úvahu, protože tímto čtvercem neprošly bóje ze všech šesti oblastí, kde se pak trosky našly – jejich souřadnice zde pak pro hledače napíšu). Danou oblastí prošlo 8 bójí, které pak doputovaly do blízkosti místa, kde se na ostrově Reunion našel flaperon, 5 bójí - kryt klapky, 2 bóje – vertikální kormidlo, 2 bóje – kryt motoru, 5 bójí – klapka křídla a 2 bóje – Mossel Bay.

Oceňuji vaši pomoc, více hlav více ví.

P.S. Převedená data včetně indexů máš v tom SRT souboru.

Výsledná "heat map" pro 6 oblastí, kde se našly trosky:
https://image.ibb.co/bZnQup/HMH370_Heat_Map.jpg

Nahlásit jako SPAM
IP: 89.177.163.–
Kevil0
Návštěvník
8. 9. 2018   #49
-
0
-

#45 Jerry
Se zobrazením není problém. Např. 7 tras bojí z nichž každá obsahuje v průměru 1 500 souřadnic se pomocí funkce

Polyline(hdc, apt, bodu);

vykreslí v C++ ihned. Časový problém byl ty bóje rychle najít a zvlášť opakovaně, když jsem ve dvou smyčkách projížděl celý Indický oceán po 1°x1°.

Nahlásit jako SPAM
IP: 89.177.163.–
Jerry
~ Anonymní uživatel
214 příspěvků
9. 9. 2018   #50
-
0
-

#46 MilanL
no filtr se udělá tak, že čáry co nechceš aby se zobrazily tak se obarví 100% průsvitnou barvou přeci se zobrazuje ARGB ne ? takže ti vlastně stačí pořád jeden jedinej soubor úseček u kterýho případně měníš jen barvu zobrazení 

Nahlásit jako SPAM
IP: 2a00:1028:83be:235a:bd89:18d2:97a3:a43b...–
Kevil0
Návštěvník
9. 9. 2018   #51
-
0
-

#50 Jerry
Nechápu, co myslíš průhlednou barvou. Podstatné je podle zadané oblasti/í vybrat dané bóje a vynést jejich trasy. Hledá se z cca 20 000 bójí, jedna bóje může mít i 5 000 GPS souřadnic.

Nahlásit jako SPAM
IP: 89.177.163.–
Jerry
~ Anonymní uživatel
214 příspěvků
10. 9. 2018   #52
-
0
-

#51 Kevil
no přeci ARGB je 32bit barva neboli TrueColor a A je průhlednost:

https://cs.wikipedia.org/wiki/Barevn%C3%A1_hloubka

, takže když máš čáru černou barvou a dáš ji průhlednost 255 tak neni vidět že jo a neni vidět ani když ona sama něco překrejvá takže se zobrazí jen to co je pod ní jako by tam nebyla.

a co se týká rychlosti vykreslování, tak 100 milionů trojůhelníků grafická karta vykreslí. grafická karta neumí vykreslovat čáry, umí jenom trojuhelníky - zobrazená čára je tak degenerovaný trojuhelník... a zvolit si oblast zobrazování u 3D enginu samozřejmě mužeš ....zkus se zeptat někde na foru o DirectX a 3D/2D grafice

jde o to, jestli chceš ty úsečky ve zvolené oblasti jenom zobrazit nebo i "zjistit" a označit v tom seznamu těch 35milionů úseček.

Nahlásit jako SPAM
IP: 2a00:1028:83be:235a:1dd5:ebce:709:503a...–
Kevil0
Návštěvník
13. 9. 2018   #53
-
0
-

#52 Jerry
Jde mi o zobrazení úseček (tras bójí), které předtím vyhledám z 20 000 bójí (35 mil. GPS souřadnic).

Nahlásit jako SPAM
IP: 89.177.163.–
Jerry
~ Anonymní uživatel
214 příspěvků
13. 9. 2018   #54
-
0
-

#53 Kevil
já vim já jenom řikám že bys moch všech těch 35 mega dat úseček narvat do grafický karty a zobrazit si jenom výřez chápeš jo ? Protože u zobrazení zadáváš XminYmin/XmaxYmax okna co chceš zobrazit. Jestli ti de jenom o zobrazení. Protože je to jednodušší:

https://docs.microsoft.com/en-us/windows/desktop/direct2d/direct2d-quickstart

https://stackoverflow.com/questions/2603276/how-do-i-clear-a-direct2d-render-target-to-fully-transparent

grafický kartě je to jedno ona ty úsečky co nejsou vidět ořeže sama a dělá to hardwarově.

Nahlásit jako SPAM
IP: 194.228.128.–
Jerry
~ Anonymní uživatel
214 příspěvků
13. 9. 2018   #55
-
0
-

#54 Jerry
https://stackoverflow.com/questions/12868543/how-to-use-drawline-in-c-directx-graphics

Nahlásit jako SPAM
IP: 194.228.128.–
MilanL+1
Věrný člen
13. 9. 2018   #56
-
0
-

tak jsem na to koukal, zatím nejlépe mi vychází pevná mřížka(matice) LATxLON  s indexy do seznamu, kde jsou seřazené boje, které měli souřadnice v daném čtverci, počet bojí v obdélníku bud jako druhý údaj v mřížce, nebo první údaj seznamu pro obdélník. Každou oblast pak stačí krátkými cykly projít mřížku od LATmin-LATmax a LONmin-LONmax a kde není index = NULL (FFFFFFFF) nebo počet 0, načíst od indexu seznam bojí do výsledku, vzhledem k seřazení použít slučování co se používá u Merge sortu - stejná čísla, duplicity přeskočit, jiná čísla vložit.

Na průnik bojí v oblastech použít opět algoritmus slučování Merge akorát s opačným efektem do konečného výsledku pouze DUPLICITY.

Druhá varianta s řídkou maticí (obdoba pole <vektor><vektor> různorozměrné (nepravidelné) 2D pole, kde každý vyšší index obsahovat různé počty nižších indexů), je pomalejší o vyhledávání místo cyklů. Nejdřív je třeba vyhledat minimální z vyšší souřadnice, u každé první vyšší mít počet nižších souřadnic (seřazených) a v nich vyhledat rozsah a opakovat pro každou další vyšší dokud není větší než max. 

První varianta je rychlejší, ale sežere víc paměti na mřížku (matici) 180x360 = 64 800 x 1 nebo 2 DWORDy (index/index+počet) pro rozlišení po ° ( při jemnějším násobky) .

Druhá varianta je pomalejší o vyhledávání, ale na mřížku spotřebuje o dost mín. paměti, tabulka s bojemi v mřížce bude stejná.

Jinak tak jak stavíš to hledání, tak je nepřesné, počítáš jen s Bojemi které v dané oblasti zaznamenali souřadnice, nepočítáš s bojemi, které danou oblastí prošli, ale vzhledem k časovému úseku měli souřadnice mimo.

Ještě by mě zajímalo jak řešíš trasu, já mám opět 2 varianty, 
Pro obě mám pomocné pole IDBojí a indexem první boje na trase.

1. varianta spočívá v seřazení záznamů (Boje, DT, LAT, LON) podle Boje a DT

2. varianta původní řazení s přidáním next indexu na další záznam pro danou boji 

Nahlásit jako SPAM
IP: 91.139.9.–
Jerry
~ Anonymní uživatel
214 příspěvků
13. 9. 2018   #57
-
0
-

#56 MilanL
pesně to co děláte sem už kdysi dávno programoval. ta oblast nebyla tak velká tedy 180000x360000 čtverců, byla jen 32000x32000, ale používal jsem tam adaptivní dělení prostoru po čtvercích a Bresenhamův algoritmus na detekci, kde se jednotlivé čáry nachází. jestli si to chcete zkusit, tak vám to někam nahraju.

Nahlásit jako SPAM
IP: 194.228.128.–
MilanL+1
Věrný člen
13. 9. 2018   #58
-
0
-

#57 Jerry
jasně přesně tak jsem to chtěl řešit, jen jsem nevěděl, že je na to pojmenovanej algoritmus, jen drobnost ty LON LAT nejsou stejný co se týče velikostí strany v podstatě °LON je v podstatě 2 násobek °LAT na rovníku, k tomu brát sférický vliv na délky LAT, ale to se u 2D nebere v úvahu, tam je pak i rozvinutá obdélníková mapa zkreslená odpovídajícím způsobem...

Nahlásit jako SPAM
IP: 91.139.9.–
Kevil0
Návštěvník
13. 9. 2018   #59
-
0
-

#54 Jerry
S grafickou karotu nemám absolutně žádnou zkušenost. Pokud jsem dáš zdroják, jak na to, vyzkouším to.

Vyhledání bójí si lze vyzkoušet, odkaz na setříděný soubor podle Data, ID, LAT, LON jsem zde uvedl o několik příspěvků výše a zkusit najít bóje, které např. prošly oblastmi:

//Reunion +-1,5
    Laa1 = -19.416;
    Laa2 = -22.416;
    Loa1 = 54.149;
    Loa2 = 57.149;

a

// Druhá oblast
    lab1 = -11.0;
    lab2 = -12.0;
    lob1 = 84.0;
    lob2 = 85.0;

Nahlásit jako SPAM
IP: 89.177.163.–
Jerry
~ Anonymní uživatel
214 příspěvků
13. 9. 2018   #60
-
0
-

#59 Kevil

"zkusit najít boje které prošli oblastmi" znamená zjistit, jestli se úsečka nebo její část nachází v daném obdélníku  a úsečka se vytvoří ze dvou po sobě jdoucích pozic jedné boje. Takže ideální je rozdělit onen prostor 180000x360000 na menší čtverce třeba 18000x36000 čtverců a pak pro každý čtverec zjistit, která úsečka ho prochází a procházející část úsečky k danému čtverci přidružit. Takže vlastně úsečky trajektorie bojí rozkouskuješ podle toho jak prochází jednotlivými čtverci. Takže když spočítám LBA nějakýho čtverce v rastru 18000x36000 třeba 256986 tak pak musim zjistit, jestli v tomhle čtverci je nějaká úsečka a přidružit ji k němu a až tohle všechno budu mít tak pak mužu začít vykreslovat podle toho jaké čtverce vidím. jde to rychle.

jestli chceš zkusit ten DirecxX tak tady je příklad na to Direct2D

https://stackoverflow.com/questions/12868543/how-to-use-drawline-in-c-directx-graphics

je to funkce
VOID DrawLine(HWND hwnd)

a je to DirectX11/12 to poznáš podle použití D2D1CreateFactory  DirectX12 Development Kit si budeš muset nainstalovat.

 

Nahlásit jako SPAM
IP: 194.228.128.–
Jerry
~ Anonymní uživatel
214 příspěvků
13. 9. 2018   #61
-
0
-

#59 Kevil
tady máš zdroják https://uloz.to/!cj3DQ1DLeyzK/robomap-zip

k tomu co děláš ale je to v C++/CLI pro MS VS 2008 SP1.

všechno co se snažíš udělat je ve funkcích

      g_ClassReg->MapViewer2D->CreateSearchingGrid();
      g_ClassReg->MapViewer2D->GridWallsAssociation_All();

Nahlásit jako SPAM
IP: 194.228.128.–
Kevil0
Návštěvník
13. 9. 2018   #62
-
0
-

#60 Jerry
Program v odkazu nefunguje, překlad hlásí chyby.  Je v něm mj.

MessageBox(NULL, TEXT("This program requires Windows NT!"), "error", MB_ICONERROR);
Nahlásit jako SPAM
IP: 89.177.163.–
MilanL+1
Věrný člen
13. 9. 2018   #63
-
0
-

#60 Jerry

ty oblasti jsou použity na vybrání bójí, u kterých se pak má vykreslit celá trasa, ne jako oblasti které se maí zobrazit.

TZN použít ten algoritmus na přidružení bojí které čtvercem procházejí.

Nahlásit jako SPAM
IP: 185.112.167.–
Kevil0
Návštěvník
13. 9. 2018   #64
-
0
-

#61 Jerry
Díky, stáhl jsem, změnil odkaz na nejnovější SDK a a zkusil přeložit. Chybí tam Segment_1h:

// stdafx.h : include file for standard system include files,
// or project specific include files that are used frequently, but
// are changed infrequently
#pragma once

// TODO: reference additional headers your program requires here

#include "c:\ROBOMAP Source Code\_common libs\Segment_1.h"

#include "Stepping.h"

#include "ProcessManagement.h"

#include "EstimatorProperties.h"

#include "StartPoseA.h"

#include "MapViewer2D.h"

#include "MapViewer_Settings.h"

#include "PenDialog.h"

#include "LSBViewer.h"

#include "RSResultsA.h"

#include "ContinualLocalizationjDE.h"

#include "Form1.h"

#include "ClassReg.h"

Nahlásit jako SPAM
IP: 89.177.163.–
Jerry
~ Anonymní uživatel
214 příspěvků
13. 9. 2018   #65
-
0
-

#64 Kevil
Ano chybí :)

jestli to chceš přeložit tak potřebuješ CELEJ !!! zdroják a všechno kolem a to má asi 300MB

opravdu to chceš ? Chceš se v tom patlat ?

tady je zbtek

https://uloz.to/!IPw5VEKFKDaH/common-libs-zip

zdroják se schovává do adresáře c:\ROBOMAP source code\

a jestli to chceš spustit musíš si nainstalovat kompletní (RS)

https://uloz.to/!p3nEyF5U8/robomap-x32-zip

nebo bych ti doporučoval stáhnout si VMWare Image kde je to připravený a stačí tam nakopírovat zdroják

https://uloz.to/!bUMLMxyG5Bic/windows-7-x32-sp1-ultimate-robomap-vmware12-rar

ale si blázen :)

Nahlásit jako SPAM
IP: 194.228.128.–
Jerry
~ Anonymní uživatel
214 příspěvků
13. 9. 2018   #66
-
0
-

#64 Kevil
Já bejt tebou zkusil bych to DirectX12 a Direct2D

https://stackoverflow.com/questions/12868543/how-to-use-drawline-in-c-directx-graphics

protože to co mám já umí kreslit úsečky jen v mřížce o velikosti 32000x32000 těch úseček muže bejt klidně 100Milionu to je fuk prostě co se vejde do paměti

Nahlásit jako SPAM
IP: 194.228.128.–
Jerry
~ Anonymní uživatel
214 příspěvků
13. 9. 2018   #67
-
0
-

#66 Jerry
ještě taková drobnost, ten zdroják ti asi nebude v MS VS 2017 fungovat protože tam nebude VisualDesigner, potřebuješ MS VS 2008.

Nahlásit jako SPAM
IP: 194.228.128.–
Kevil0
Návštěvník
13. 9. 2018   #68
-
0
-

#66 Jerry
Díky za snahu, ale v C++ jsem v podstatě začátečník. Na takové rozsáhlé projekty nemám. Pokud mi sem někdo nedá kód, jak ty bóje z dat najít (pomocí funkcí grafické karty) a vykreslit pomocí DirectX12, tak je hotovo.

Nemám problém vykreslit trasy pomocí GDI Polyline viz můj výsledek C++ a x64 assembler ;-)

https://image.ibb.co/d3hzx9/7_b_j.jpg

Nahlásit jako SPAM
IP: 89.177.163.–
Jerry
~ Anonymní uživatel
214 příspěvků
13. 9. 2018   #69
-
0
-

#68 Kevil
no zdroják jsem ti poslal ale je to kousek zdrojáku z celýho projektu kterej má 300Mega a je to v MS VS 2008 SP1 C++/CLI pod Windows 7 x32 a bez AERA !!!!

je to přesně to co děláš, rozměry mřížky jsou max. 32000x32000 buněk a zakresluje to úsečky.

bohužel naučit programovat se asi budeš muset sám

zkus to zapsání těch 100mega úseček do grafický paměti pomocí DirectX2D

ten příklad je tady

https://stackoverflow.com/questions/12868543/how-to-use-drawline-in-c-directx-graphics

Nahlásit jako SPAM
IP: 194.228.128.–
Jerry
~ Anonymní uživatel
214 příspěvků
13. 9. 2018   #70
-
0
-

#69 Jerry
ještš taková drobnost, ten příklad C++/CLI co sem ti poslal tak ten samozřejmě umí i dynamicky zoomovat na určitou část a děláš to myší a je to stejný jako když kreslíš třeba v autocadu, ten zdroják je prostě delší no má ai 60000 řádků v C++ ale dost těžko ho asi zkrátíš.

Nahlásit jako SPAM
IP: 194.228.128.–
Kevil0
Návštěvník
13. 9. 2018   #71
-
0
-

#69 Jerry
Není mi jasný, jak mi DirectX2D zrychlí vykreslení trasy po úsečkách, když nyní používám jeden příkaz na vykreslení celé trasy (5 000 "úseček") pomocí GDI Polyline ?

Jak píšeš o tom zdrojáku, tak nemám problém s jakoukoliv velikostí, musí jít ale přeložit pomocí Visual Studio 2017. Nechápu proč má 60 000 řádků. Se zoomováním ve svém programu pomocí myši počítám taky, ale vidím to na max. 50 řádků :-).

Nepotřebuji použít nějaký hotový program, musím ale jasně vědět, jak danou funkci použít ideálně na příkladu. Nebráním se zkusit pro vyhledání bójí použít funkce grafické karty, ale vůbec netuším, jak jí předat údaje o 20 000 bójích a 35 mil. GPS souřadnic.

Pokud se v tom vyznáš, tak mi prosím napiš, jak mám data načíst do paměti grafické karty, najít podle dvou oblastí bóje, jejichž trasy prošla alespoň jednou oběma oblastmi a jak nalezené trasy bójí zobrazit.

Nahlásit jako SPAM
IP: 89.177.163.–
Jerry
~ Anonymní uživatel
214 příspěvků
14. 9. 2018   #72
-
0
-

#71 Kevil
Když zvládnež algoritmus na zoomování na 50 řádcích tak ok. a co se týče DirectX2D tak hotovej příklad je tady

https://stackoverflow.com/questions/12868543/how-to-use-drawline-in-c-directx-graphics

Musíš si nainstalovat DirectX12 Development Kit. Grafická karta pracuje jen s trojuhelníky, takže i když kreslíš čáru ve 2D tak sse stejně předává trojuhelník, kde 2 bodu jsou totožné. Takže jednoduše nasypeš do bufferu paměti grafické karty 35 milionu úseček a necháš je vykreslit, ale protože neumíš DirectX tak stejně nebudeš chápat zdroják. Proto asi budeš muset začít odzačátku:

http://www.directxtutorial.com/legacylist.aspx

na tvým místě bych si vybral DirectX9 protože je to asi .. jednodušší když nic nevíš.

Nahlásit jako SPAM
IP: 2a00:1028:83be:235a:e973:c0e0:63b0:c094...–
Kevil0
Návštěvník
14. 9. 2018   #73
-
0
-

#72 Jerry
Předpokládám, že se v tom DirextX12 vyznáš. Rady typu ať si to nastuduji od začátku jsou mi na nic. Takhle bych si nedovolil někomu "radit". Pokud sem neuvedeš krátké příklady, jak předat data do paměti, najít bóje pomocí dvou zadaných oblastí a jak je vykreslit, tak je hotovo. Pokud víš jak na to, tak to přece nemůže být žádná věda. Fakt to nebudu zkoumat, když dopředu nevím, zda DirectX12 potřebné funkce vůbec má. Odkaz na ukázku "How to use DrawLine in C++ (DirectX Graphics)" je o ničem...

Nahlásit jako SPAM
IP: 89.177.163.–
MilanL+1
Věrný člen
14. 9. 2018   #74
-
0
-

trošku jsem přemýšlel nad tou vaší diskusí s využitím GK, já bych jí v tomhle programu použil na něco úplně jiného, při šikovné organizaci dat, bych GK využil na konverzi LATxLON, ikdyž ten efekt vzhledem k tomu filtru na několik vybraných bojí asi nebude zas tak velkej.

 pro c++ je jedna zajímavá utilitka pro distribuci výpočtů na GK AMP, navíc je to hodně primitivní na naučení, odhadem, tak 1-2 dny víc ne.

rozdíly mezi CPU - OpenCL - CUDA - AMP  http://ceur-ws.org/Vol-1746/paper-23.pdf

tutorial AMP https://download.microsoft.com/download/4/0/E/40EA02D8-23A7-4BD2-AD3A-0BFFFB640F28/CppAMPLanguageAndProgrammingModel.pdf

prezentace https://channel9.msdn.com/Events/BUILD/BUILD2011/TOOL-802T  ukázka výkonu od cca 5min

Nahlásit jako SPAM
IP: 91.139.9.–
Jerry
~ Anonymní uživatel
214 příspěvků
14. 9. 2018   #75
-
0
-

#74 MilanL
MS AMP využívá pro výpočty jádra procesoru !!! CUDA využívá grafický procesor na grafické kartě. Tak abyste to nepopletli.

Nahlásit jako SPAM
IP: 2a00:1028:83be:235a:e973:c0e0:63b0:c094...–
Jerry
~ Anonymní uživatel
214 příspěvků
14. 9. 2018   #76
-
0
-

#73 Kevil

když neumíš nic z DirectX tak asi těžko napíšeš "něco". nicméně to co chceš je jednoduché a je to v podstatě úvodní příklad do výuky DirectX. Přesně podle vzoru na  http://www.directxtutorial.com/…st.aspx ; akorát místo trojuhleníku budeš kreslit úsečky takže ty máš úsečku danou dvěma body P1(x1,y1), P2(x2,y2) a trojuhelník má 3 body. Takže zadáš P1(x1,y1), P2(x2,y2), P3(x1,y1), ano vidíš správně, úsečka se udělá tak, že dva body jsou v trojuhelníku stejné a protože programuješ v native C++ pod MS VS tak sem tě odkázal na Native DirectX příklady v C++, kdybys dělal v .NET odkázal bych tě na SharpDX, SlimDX nebo Unity3D knihovnu. Obávám se, že naprogramovat si to budeš muset sám. :)

Nahlásit jako SPAM
IP: 2a00:1028:83be:235a:e973:c0e0:63b0:c094...–
Jerry
~ Anonymní uživatel
214 příspěvků
14. 9. 2018   #77
-
0
-

#75 Jerry
a GPU taky :)

Nahlásit jako SPAM
IP: 194.228.128.–
MilanL+1
Věrný člen
14. 9. 2018   #78
-
0
-

#75 Jerry

divný já ten AMP pochopil tak, že to prostřednictvím directx v rámci možností portuje na GK.

A rozdíl mezi SDK pro Cuda, OpenCL a AMPem je ten, že u AMPu se jedná jen o malou úpravu kodu v C++ a nemusíš se učit DX, Cuda ani openCL.

z 1 diplomky

Platform model pro C++ AMP využívá pro paralelní zrychlení grafické karty s podporou
DirectX 11. Tím pádem není omezena pouze na grafické čipy firmy NVIDIA, ale podporuje
i AMD. Struktura platform modelu vychází z modelu OpenCL viz Obr. 1. DirectX 11
zařízení lze ale také simulovat jako Microsoft DirectX REF device, WARP (zrychlení
pomocí instrukcí SSE) nebo přímo procesorem. [8]

C++   AMP   (C++   Accelerated   Massive   Parallelism)
[Mil1] accelerates the execution of C++ code by taking
advantage    of    the    data-parallel    hardware    that's
commonly present as a graphics processing unit (GPU)
on a discrete graphics card. C++ Accelerated Massive Parallelism
(C++   AMP)   is   a   native   programming
model   that   contains   elements   that   span   the
C++ programming   language and   its runtime   library.
C++ AMP    is    a library implemented    on DirectX    11
and an open  specification from Microsoft for  implementing
data  parallelism  directly  in  C++.This  language  is
easier  to  use  and  contains  many  libraries  for  building
data-parallel applications.

V tom videu je to myslím ukázaný, základní běh, multitasking na CPU a s AMPem, myslím že bez grafiky by ten rozdíl nemohl nikdy být tak výrazný.

Nahlásit jako SPAM
IP: 185.112.167.–
Jerry
~ Anonymní uživatel
214 příspěvků
14. 9. 2018   #79
-
0
-

#78 MilanL
jo já vim GPU taky ... oni to tam dodělali od roku 2015 ...

Nahlásit jako SPAM
IP: 194.228.128.–
Kevil0
Návštěvník
14. 9. 2018   #80
-
0
-

#74 MilanL
Díky, díval jsem se na to, ale bohužel tam není nějaká praktická ukázka.

Pro představu nyní trvá mému programu 7 minut, než spočítá součin počtu bójí pro 9 míst s nalezenými troskami (+/- 0,5°) a cyklem, který projíždí oblast Indického oceánu po 1°x1° od 0° až 40° S a 80° až 108° E. Pro každou z 9 oblastí to představuje 41*29 čtverců = 1 189. V každém čtverci se z 20 000 bójí, které obsahují 35 mil. GPS souřadnic, hledá počet bójí, které se pohybovaly v místě nálezu jedné z devíti trosek a aktuálním čtvercem 1°x1°. Výsledkem je heat mapa 41*29, kde je v každém čtverci součin nalezených bójí (výchozí hodnotu jsem samozřejmě nastavil na 1). Nejvyšší hodnota 4 599 504 je ve čtverci 24 S 81 E (na jedno z devít míst nálezů tak v půměru doplulo 4 599 504 ^ (1/9) = 5,50 bójí) pak udává místo, které lze s nejvyšší pravděpodobností považovat za místo, odkud začalo svou dráhu všech devět trosek do míst svých nálezů.

Nahlásit jako SPAM
IP: 89.177.163.–
Zjistit počet nových příspěvků

Přidej příspěvek

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 41 hostů

Podobná vlákna

Binární strom — založil Michaela

Binární číslo — založil pazdy

Binární vyhledávání — založil K4BlOs

Binární kód — založil wokena

Binární operace — založil Holden

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032018 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý