Stran 1 od 1

unikatna vsota števil

Objavljeno: 2.12.2005 8:22
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

Objavljeno: 2.12.2005 10:14
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?

pozabil

Objavljeno: 2.12.2005 11:43
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]

Objavljeno: 2.12.2005 12:20
Napisal/-a Roman
Koliko vektorjev pa imaš?

okrog 1000

Objavljeno: 2.12.2005 13:56
Napisal/-a y0gie
Okrog 1000 vektorjev. (trenutno je max. število 1001).

Objavljeno: 2.12.2005 19:04
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) :?

malo več detajlov

Objavljeno: 2.12.2005 21:44
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 ?

Objavljeno: 2.12.2005 22:11
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)

Re: malo več detajlov

Objavljeno: 4.12.2005 23:02
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

Objavljeno: 5.12.2005 8:20
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.

Objavljeno: 5.12.2005 10:33
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..

Objavljeno: 5.12.2005 11:44
Napisal/-a Roman
Moram priznati, da tega nisem vedel.

Objavljeno: 5.12.2005 13:12
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..