Hollosi Information eXchange /HIX/
HIX CODER 1326
Copyright (C) HIX
2001-10-19
Új cikk beküldése (a cikk tartalma az író felelőssége)
Megrendelés Lemondás
1 Re: kereses 16 jegyu szamok kozt (mind)  42 sor     (cikkei)
2 java kerdesek (mind)  5 sor     (cikkei)
3 EPSON kodok (mind)  10 sor     (cikkei)
4 RE: *** HIX CODER *** #1325 (mind)  10 sor     (cikkei)
5 Re: *** HIX CODER *** #1325 (mind)  16 sor     (cikkei)
6 Re: String cserebere (mind)  52 sor     (cikkei)
7 Re: kereses (mind)  29 sor     (cikkei)
8 Magic (mind)  6 sor     (cikkei)
9 Re: kereses (mind)  19 sor     (cikkei)
10 Re: String cserebere (mind)  13 sor     (cikkei)

+ - Re: kereses 16 jegyu szamok kozt (mind) VÁLASZ  Feladó: (cikkei)

, Oct 17 2001, CODER #1325:
> Egy olyan problemam lenne, hogy egy 10-20000 db 16 jegyu
> szam kozott kellene keresgelni.
> A program indulasakor viszonylag tobb idom van es az sem gond
> ha lefoglalok 10-20 Mb-t a ram-ban. A hangsuly azon van hogy
> a kereses nagyon gyors legyen. Mit javasolnatok ?
> ui.: a rendezes es a logaritmikus kereses mar eszembe jutott...

a rendezés, logaritmikus keresés memóriában majdnemhogy tökéletes,
hiszen max 14-15 lépésben megtalálod vele a számodat, és alig
igényel programozást (qsort, bsearch megvan C-ben,
STL vector<>, set<> megvan c++ban).

Ha azonban a feladat mint kihívás is izgat, akkor valamilyen
egyedi függvénnyel dolgozó hash módszer tűnik ígéretesnek.
Ha ugyanis eléggé speciálisak a számok tulajdonságai,
esetleg jobban jársz, mint az általános bináris kereséssel.
Ehhez azonban jó lenne tudni valamit a számok _eloszlásáról_,
és más tulajdonságáról.
pl mennyire egyenletesen töltik ki az értékkészletet? van-e jelentős
torlódás? ismétlődő jegyek a számokban?

a technikai részletek:
16 jegyű szám alatt mit értünk? Egész vagy lebegőpontos
számokról van szó?

10 byte-os long double, 4 byte-os egész?
ezekre valami kis okos hash függvényt kellene kitalálni

stringben tárolt egész szám?
ezeket pl lehetne
- 64 bites egészekké alakítani, vagy
- huffmann kódolással tömöríteni, ekkor
gyakorlatilag egy szótárt készítenél belőlük, amiben szintén
nagyon gyorsan lehet keresni.

szóval ha izgatnak a feladatok, itt az alkalom...
szvsz ilyen feladatokra a c++ Standard Template Library-ja
nagyon szemléletes megoldást tud nyújtani lásd pl map<>
-- 
Józsi

+ - java kerdesek (mind) VÁLASZ  Feladó: (cikkei)

Sziasztok!

A Java csak magancelra ingyenes, vagy el is adhatom amit
fejlesztek?
Mr.Bab
+ - EPSON kodok (mind) VÁLASZ  Feladó: (cikkei)

Sziasztok.

Meg tudna valaki irni, hogy az EPSON matrixnyomtatokat hogy lehet vezerelni?
[betutipus, alahuzas, betumeret, stb.]

Kosz:
Gaby
PS: Cc maganba is, please
________________________________________________________________________
  +  http://www.sch.bme.hu/~gyoreg  +  ICQ:19934854
+ - RE: *** HIX CODER *** #1325 (mind) VÁLASZ  Feladó: (cikkei)

> egy olyan (parancssoros, DOS/Win32 alatt futo) program erdekelne, amely
> ... lecsereli s1-et s2-re ....

Hello!

Valamikor (~10 evvel ezelott) volt ilyesmi nekem. Irj maganba ha
erdekel es megkeresem.

Sincerely,
Attila Voros, Chief Engineer, ISDgames
+ - Re: *** HIX CODER *** #1325 (mind) VÁLASZ  Feladó: (cikkei)

Üdv

> Vagy egyszerubb es gyorsabb, ha az ember fia megirja sajat maganak? :)
Az a leggyorsabb :)
Egy ciklus az egesz.

> Egy olyan problemam lenne, hogy egy 10-20000 db 16 jegyu szam kozott
kellene
> keresgelni.
> Mit javasolnatok ?
Ha a program indulasakor rendezed az adatokat (pl. quicksorttal), akkor
szemely szerint binaris keresest ajanlok.
Ha overflow, akkor konvertald a 10es szamrendszert 36osra
(0,1,...,9,A,B,C,...,Z) es ugy keress benne.
üdv
D@xi
+ - Re: String cserebere (mind) VÁLASZ  Feladó: (cikkei)

On 17 Oct 01, at 14:33,  wrote:

> Haliho,

szia,

>  egy olyan (parancssoros, DOS/Win32 alatt futo) program erdekelne,
> amely kepes arra, hogy a megadott file-okban (amelyek akar
> binarisak is lehetnek!) lecsereli s1-et s2-re, vagyis olyan, mint a
> TR, csak eppen stringekkel dolgozik. Letezik valami Linux ala irt
> free cucc? Vagy egyszerubb es gyorsabb, ha az ember fia megirja
> sajat maganak? :)

Ha jol ertem, akkor arra gondolsz, hogy pl. egy GNU utility win32-
re portolt valtozata jo lenne. (Egyebkent a GNU nem kotodik a
Linux-hoz automatikusan, szoval attol, hogy Linux alatt azt
hasznaljak, attol a GNU-sok jobb szeretik GNU-nak nevezni, nem
"Linux ala irt free cucc"-nak)

Ha ismered a tr-t, akkor bizonyara hallottal a sed-rol is. A GNU sed
info-jaban ez van:

About the (non-)limitations on line length
******************************************

   For those who want to write portable SED scripts, be aware that some
implementations have been known to limit line lengths (for the pattern
and hold spaces) to be no more than 4000 bytes.  The POSIX.2 standard
specifies that conforming SED implementations shall support at least
8192 byte line lengths.  GNU SED has no built-in limit on line length;
as long as SED can malloc() more (virtual) memory, it will allow lines
as long as you care to feed it (or construct within it).

Szoval ha binaris a file, es sokaig nem lenne benne \n karakter,
akkor sem esik ketsegbe, a teljes file is lehet egy szem sor. s1 s2-
re cserelese 'sed -e s/s1/s2/g file' modon megy. Az sem kell a
GNU sed-nek, hogy az utolso sor le legyen zarva \n-nel.

dos/win alatt ciki, hogy a sorvegjel \r\n szokott lenni. A unix
progikat ugy szoktak portolni, hogy megegye a szovegfile-t akkor
is, ha csak \n, meg akkor is, ha \r\n van a vegen. Iraskor pedig
elkepzelheto, hogy mindig \r\n-t ir ki egy progi. Most megneztem a
sed cygwin-es valtozatat, es elfogadja mindket sorvegjelet, kiirni
pedig egyetlen \n-et ir. Ez ciki, mert ha a binaris file-ban veletlenul
\r\n van egymas mellett, akkor a \r eltunik. Valahogy lehet a
cygwin-ben szabalyozni, hogy binaris file-kent kezeljen mindent
(tehat ne vegye figyelembe, ne hagyja ki a \r-et), de most hiretlen
nem jut eszembe a reszletes modja. Mindenfelekeppen nezd meg
szerintem a forrast, es ellenorizd benne, hogy ugy forduljon le a
gepeden, hogy veletlenul se szoveges modban nyissa meg a file-t.

István
+ - Re: kereses (mind) VÁLASZ  Feladó: (cikkei)

On 17 Oct 01, at 10:53,  wrote:

> Sziasztok !

Szia,

> Egy olyan problemam lenne, hogy egy 10-20000 db 16 jegyu szam
> kozott kellene keresgelni. A program indulasakor viszonylag tobb
> idom van es az sem gond ha lefoglalok 10-20 Mb-t a ram-ban. A
> hangsuly azon van hogy a kereses nagyon gyors legyen. Mit
> javasolnatok ?
> ui.: a rendezes es a logaritmikus kereses mar eszembe jutott...

Gondolom binaris keresest ertesz logaritmikus alatt.

Amennyiben ki tudsz talalni egy jo Hash fuggvenyt, ami jol
szetszorja a keresendo szamokat (ilyen fuggvenyt a szamoktol
fuggoen kell kitalalnod, szoval nem lehet ra altalanos tippet adni),
akkor erdemes azzal tobb darabra osztani a keresest. Pl. ha a
szam valamelyik (mondjuk utolso) byte-ja elegendoen egyenletes
eloszlasban felveszi kozel mind a 256 fele erteket, akkor azt
hasznalhatod Hash kodnak, amivel a szamokat egy 256 elemu
tombbel 256 fele rekeszbe osztod, amiken belul pl. binaris
keresest csinalsz.

Ha meg tobb memoriat is hasznalhatsz, csinalj 16 bites hash
kodot :)

István
+ - Magic (mind) VÁLASZ  Feladó: (cikkei)

Sziasztok,
Nem ismer valaki olyan budapesti cégeket amelyek Magic környezetben fejlesztene
k? (esetleg keresnek fejlesztőket)
köszönet

(webes bekuldes, a bekuldo gepe: koszta.internal.nextra.hu)
+ - Re: kereses (mind) VÁLASZ  Feladó: (cikkei)

 wrote:
> Sziasztok !

> Egy olyan problemam lenne, hogy egy 10-20000 db 16 jegyu szam kozott kellene
> keresgelni.
> A program indulasakor viszonylag tobb idom van es az sem gond ha lefoglalok
> 10-20 Mb-t a ram-ban. A hangsuly azon van hogy a kereses nagyon gyors
> legyen.
> Mit javasolnatok ?

> Kosz
> PKA

> ui.: a rendezes es a logaritmikus kereses mar eszembe jutott...

javaslom D.E.Knuth: a proramozas muveszete cimu konyvet. 3 kotetes, es az
egyik kotet (cca 500 o., de lehet tobb is) csak ilyen problemaval
foglalkozik.
homer
+ - Re: String cserebere (mind) VÁLASZ  Feladó: (cikkei)

 wrote:
> Haliho,

>  egy olyan (parancssoros, DOS/Win32 alatt futo) program erdekelne, amely
> kepes arra, hogy a megadott file-okban (amelyek akar binarisak is lehetnek!)
> lecsereli s1-et s2-re, vagyis olyan, mint a TR, csak eppen stringekkel
> dolgozik. Letezik valami Linux ala irt free cucc? Vagy egyszerubb es
> gyorsabb, ha az ember fia megirja sajat maganak? :)

javasom nezd meg a sed nevu proggyt linux alatt. nem tudom fog-e binaris
allomanyokon muxeni. szerintem ez megvan dos-os valtzoatban is, ha mast
nem, akkor a sygnus cucc alatt tud futni vindoze kornyezetben dos ablakban
homer

AGYKONTROLL ALLAT AUTO AZSIA BUDAPEST CODER DOSZ FELVIDEK FILM FILOZOFIA FORUM GURU HANG HIPHOP HIRDETES HIRMONDO HIXDVD HUDOM HUNGARY JATEK KEP KONYHA KONYV KORNYESZ KUKKER KULTURA LINUX MAGELLAN MAHAL MOBIL MOKA MOZAIK NARANCS NARANCS1 NY NYELV OTTHON OTTHONKA PARA RANDI REJTVENY SCM SPORT SZABAD SZALON TANC TIPP TUDOMANY UK UTAZAS UTLEVEL VITA WEBMESTER WINDOWS