unikatna vsota števil

O matematiki, številih, množicah in računih...
Odgovori
y0gie
Prispevkov: 4
Pridružen: 2.12.2005 8:13

unikatna vsota števil

Odgovor Napisal/-a y0gie »

Zdravo

Mene zanima če bi se dalo pretvorit vektor števil tako, da bi vedno dobil unikatno število.

[1,6,3,2,1,8] = ?
[8,1,3,6,1,2] = ?
[6,6,6,6,6,6] = ?
[1,7,8,9,3,2] = ?

Rad bi dobil ven vedno različen rezultat (eno število). Enak rezultat bi podali kvečjemu vektorji z enakim zaporedjem in velikostjo. ([1,2,3,4,5] , [1,2,3,4,5]).

Lp,
y0gie

Roman
Prispevkov: 6598
Pridružen: 21.10.2003 8:03

Odgovor Napisal/-a Roman »

Če so komponente enomestne (enice), ni noben problem, zapišeš jih po vrsti v desetiškem zapisu, pa je. Noben problem ni tudi sicer, če so komponente večje. Ugotoviš največjo možno in jo vzameš za številsko osnovo. A kaj ti bo vendar tak zapis?

y0gie
Prispevkov: 4
Pridružen: 2.12.2005 8:13

pozabil

Odgovor Napisal/-a y0gie »

Pozabil sem podat pomemben podatek. Številka (identifikator vektorja) mora biti kvečjemu 2 mestno število [0,99].

Na sestavljanje števil sem že pomislil, ampak potem je številka predolga (največ 18 mestna je lahko)

V bistvu imam takšne podatke: komponente vektorja - 11,12,13,...,50
vektorji so 12 mestni [11,16,13,27,47,34,41,50,11,22,34,34]

Roman
Prispevkov: 6598
Pridružen: 21.10.2003 8:03

Odgovor Napisal/-a Roman »

Koliko vektorjev pa imaš?

y0gie
Prispevkov: 4
Pridružen: 2.12.2005 8:13

okrog 1000

Odgovor Napisal/-a y0gie »

Okrog 1000 vektorjev. (trenutno je max. število 1001).

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Odgovor Napisal/-a Aniviller »

Ce je to da so komponente manjse od 100 edin pogoj potem krajse kot 24 mest ni mogoce. (toliko je pac kombinacij) Ce najdes se kaksno korelacijo potem se da pomagat. Ce te moti da v racunalnik ne spravis toliksne stevilke predlagam da indeksiras z dvemi "long" ali pa kar z byte-i (ne vem kaj konkretno rabis) :?

y0gie
Prispevkov: 4
Pridružen: 2.12.2005 8:13

malo več detajlov

Odgovor Napisal/-a y0gie »

se opravičujem. Nisem mel časa razložit celotnega problema, kot bi verjetno moral.
Stvar je taka. Gre za računalniški program, kjer lahko uporabniki vpisujejo določene kombinacije črk in številk. (največ 12 mestno kombinacijo). npr. AGTR002ARU, TZEWGGG0001, TRZZZZZ01, TR01ZZZZZ,... Te kombinacije se shranjujeo v bazo in jih je trenutno okrog 40000, pričakujem pa da se bo ta številka povečala za 2000000. Trenutno traja povpraševanje ali neka kombinacija že obstaja v bazi kakšni 2 sek.
Moja želja je pretvoriti String (kombinacijo) v neko številsko obliko (ker baza dosti hitreje dela na B-drevesu s števili, kot pa z znaki). koliko sem stvar pretestiral bi na 40000 zapisih potem povpraševanje trajalo 40 ms. Še bolje pa je če bi lahko povpraševanje naredil na način, kjer podam max. in min. kombinacije, potem bi moralo to bit nekje med 10 in 20 ms.

Kakorkoli...

Uspelo mi je rešiti do določene mere ta problem. Ustvaril sem index v bazi (zraven kombinacije), ki unikatno določa kombinacijo. Prvo kar naredim je da vsakemu znaku priredim desetiško število, urejeno po velikosti (0 = 1, 1=2, ... A= 10, ...), potem pa postavim vse znake na levo stran, število pa ostane na koncu. tako dobim iz npr. RTZARR900EE - RTZARREE900. Potem kombinacijo pretvorim v 40-tiški zapis. To ustvari število max. dolžine 20 (tip gre v long, torej je manj ko 2 na 64).

Problem nastane pri kombinacijah ki imajo števila razmetana po kombinaciji .. npr. RTA9Z0R0TU.

Tukaj se mi zalomi.

Ma kdo kakšno drugačno idejo ali kakšen pameten predlog ?

Uporabniški avatar
Aniviller
Prispevkov: 7263
Pridružen: 15.11.2004 18:16

Odgovor Napisal/-a Aniviller »

Ce rabis samo alfanumerike, potem si verjetno ze poskusil stvar spravit v 64=2^6, kar pa na zalost pride 2^72... Ce imas stevilo moznih znakov znatno manjse od 64 je verjetno najpametneje da res pretvoris na tisto bazo, kot si ze na zacetku omenil. Ce imas razlicnih znakov cca. 36 ti pride z zdruzevanjem po dveh znakov do 2^11, torej 2^66 za celoten string. Ce grupiras po 4 bi moralo priti brez tezav v long. 8)

Uporabniški avatar
GJ
Prispevkov: 2635
Pridružen: 27.1.2003 22:08

Re: malo več detajlov

Odgovor Napisal/-a GJ »

y0gie napisal/-a:Ma kdo kakšno drugačno idejo ali kakšen pameten predlog ?
Klasična metoda, ki ti stvar pohitri na nekaj 10 mikro sekund pri nekaj miljonih 'itemov' je kvadratična. Torej uporabi 'hash' metodo.

LP :lol: GJ

Roman
Prispevkov: 6598
Pridružen: 21.10.2003 8:03

Odgovor Napisal/-a Roman »

Jaz sploh ne bi kompliciral. Uporabil bi 12 mesten alfanumeričen ključ in indeksiral po njem. Ko bi se nabralo toliko podatkov, da bi sistem klecnil, bi kupil boljši računalnik, ki bi se v tem času pojavil po sprejemljivi ceni na tržišču.

Uporabniški avatar
GJ
Prispevkov: 2635
Pridružen: 27.1.2003 22:08

Odgovor Napisal/-a GJ »

Roman napisal/-a:Jaz sploh ne bi kompliciral.
Če ne rabiš hitrega odziva vsekakor.
V nasprotnem primeru pa dobro optimizirana kvadratična metoda pohitri odzivnost sistema pri zelo velikih poljih za vsaj tisočkrat.

Lep dan želim..

Roman
Prispevkov: 6598
Pridružen: 21.10.2003 8:03

Odgovor Napisal/-a Roman »

Moram priznati, da tega nisem vedel.

Uporabniški avatar
GJ
Prispevkov: 2635
Pridružen: 27.1.2003 22:08

Odgovor Napisal/-a GJ »

Roman napisal/-a:Moram priznati, da tega nisem vedel.
Osnovna ideja algoritma kvadratične metode indeksiranja je dokaj preprosta.

Naj najprej na hitro razložim pomen termina 'hash'.
V našem primeru je vrednost 'hash' indeksna vrednost iskanega/vloženega niza, ki jo dobimo po neki enačbi. Metod za izračun vrednosti 'hash' je več, v odvisnosti od vrste podatkov, ki jih želimo indeksirati.

Najprej določimo območje variable 'hash', ki določa faktor za kolikokrat bo iskanje hitrejše. Recimo da hočemo iskanje pospešiti za 256 krat. V tem primeru nam tip variable 'hash' predstavlja velkost spominske celice enega byte-a (v en byte lahko spravimo število med 0 in 255).

Bazo podatkov razdelimo na 256 pod enot, vsako pa naslavlja 'hash' vrednost torej število med 0 in 255.

Vzamimo za 'hash' metodo navaden 'CheckSum'. Vrednost 'hash' nekega niza, ki ga iščemo v bazi je enaka vsoti vseh byte-ov karakterjev tega niza. Ker je variabla 'hash' velikosti enega byta dejansko uporabimo zgolj zadnjih osem bitov 'CheckSum'-a za naš 'kvadratični' index.

Torej, ko išemo neko vrednost niza v bazi najprej izračunamo 'hash' vrednost, ki nam pove v katerem delu baze moramo nadaljevati iskanje.
Tako smo v našem primeru pohitrili iskanje za približno 256 krat. (Govorimo seveda zgolj o hitrosti iskanja in ne tudi o času, ki je potreben za prenos in obdelavo informacij).

Max. vrednost variable 'hash' (določa tudi število podmožic podatkov) je programsko poljubna. Določimo jo glede na pričakovano število indexov in željeno hitrost odziva.

Lep dan želim še naprej..

Odgovori