[JATEK] - Nagy mennyiségű adat összefésülése
2018-05-25T20:42:40+02:00
2018-06-07T17:42:42+02:00
2022-07-21T05:38:20+02:00
  • Amelyik db kezelő tud párhuzamosítani, illetve hash match-elni, az szerintem hasonló eredményt fog hozni.
    Mutasd a teljes hozzászólást!
  • Szerintem ez is egy fontos teszt, jó lenne, ha lenne több féle adatbázis motoron lefutatott teszt.

    Újabb Delphis megoldás:

    Idő: ~560Ms
    Count: 211092

    program project13; {$APPTYPE CONSOLE} uses generics.collections, generics.defaults, Classes, dateutils, SysUtils; type pls = ^tls; tls = record word: string[31]; end; ppositon = ^TPosition; TPosition = record pos1: integer; pos2: integer; end; str3 = string[3]; Tpositions = Tlist; TdictIndex = Tdictionary<str3, Tpositions>; type { TThreadSearch } TThreadSearch = class(TThread) public StartFrom: integer; Endit: integer; SearchInThis, ListPartWords: Tlist; counter: integer; ldict: TdictIndex; procedure Execute; override; end; //MainVarBegin var SearchInThis, ListPartWords: Tlist; s: string[31]; i: integer; counter: integer; filename: string; time: TDateTime; threadcount: integer; threadlist: TObjectList<TThreadSearch>; lThreadSearcher: TThreadSearch; threadsFinisshed: boolean; lthreadfinisshed: boolean; dict: TdictIndex; //MainVarEnd procedure TThreadSearch.Execute; var i, m: integer; positionList: Tpositions; lhash: str3; pos1, pos2, lastpos: integer; pat, text: string[31]; begin self.counter := 0; for i := StartFrom - 1 to Endit - 1 do begin lhash := ''; pat := tls(ListPartWords[i]^).word; lhash := copy(pat, 1, 3); if ldict.containskey(lhash) then begin positionList := ldict[lhash]; lastpos := -1; for m := 0 to positionList.Count - 1 do begin pos1 := TPosition(positionList[m]^).pos1; if lastpos <> pos1 then begin pos2 := TPosition(positionList[m]^).pos2; text := tls(SearchInThis[pos1]^).word; if pos(pat, text, pos2) > 0 then begin inc(self.counter); end; end; lastpos := pos1; end; end; end; self.Suspended := True; end; Procedure IndexProc(i: integer; ThreadID: integer); var b: integer; positionList: Tpositions; word: string[31]; lint: str3; obj: ppositon; begin word := tls(SearchInThis[i]^).word; lint := ''; for b := 1 to length(word) - 2 do begin lint := copy(word, b, 3); if not dict.containskey(lint) then begin positionList := Tpositions.create; dict.Add(lint, positionList); new(obj); obj.pos1 := i; obj.pos2 := b; positionList.Add(obj); end else begin positionList := dict[lint]; new(obj); obj.pos1 := i; obj.pos2 := b; positionList.Add(obj); end; end; end; Procedure ReadList(var list: Tlist; iFilename: String; dict : TdictIndex); var tfIn: TextFile; nw: pls; Buf: array [1 .. 8192] of Char; i: integer; begin try AssignFile(tfIn, iFilename); SetTextBuf(tfIn, Buf); reset(tfIn); while not EOF(tfIn) do begin readln(tfIn, s); new(nw); list.Add(nw); tls(nw^).word := s; end; if dict<>nil then begin for i := 0 to list.Count - 1 do begin IndexProc(i, 1); end; end; except end; CloseFile(tfIn); end; begin try WriteLn('Number of core and threads:'); dict := TdictIndex.create(); readln(threadcount); SearchInThis := Tlist.create; ListPartWords := Tlist.create; time := now(); filename := ExtractFilePath(ParamStr(0)) + 'words_100K.txt'; WriteLn('Reading the contents of file: ', filename); ReadList(SearchInThis, filename,dict); WriteLn('Read 100k and indexing: ' + IntToStr(MilliSecondsBetween(now, time))); filename := ExtractFilePath(ParamStr(0)) + 'words_35K.txt'; WriteLn('Reading the contents of file: ', filename); ReadList(ListPartWords, filename,nil); threadlist := TObjectList<TThreadSearch>.create; for i := 0 to threadcount - 1 do begin lThreadSearcher := TThreadSearch.create(True); lThreadSearcher.SearchInThis := SearchInThis; lThreadSearcher.ListPartWords := ListPartWords; lThreadSearcher.ldict := dict; lThreadSearcher.StartFrom := (trunc(ListPartWords.Count / threadcount) * i) + 1; lThreadSearcher.Endit := trunc(ListPartWords.Count / threadcount) * (i + 1); WriteLn('Thread No' + IntToStr(i + 1) + ' From: ' + IntToStr(lThreadSearcher.StartFrom) + ' - To:' + IntToStr(lThreadSearcher.Endit) + ''); threadlist.Add(lThreadSearcher); lThreadSearcher.start; end; while True do begin threadsFinisshed := True; for i := 0 to threadcount - 1 do begin lthreadfinisshed := threadlist[i].Suspended; threadsFinisshed := lthreadfinisshed and threadsFinisshed; end; if threadsFinisshed then break; sleep(5); end; counter := 0; for i := 0 to threadcount - 1 do begin counter := counter + threadlist[i].counter; end; WriteLn('Count: ' + IntToStr(counter)); WriteLn('Time:' + IntToStr(MilliSecondsBetween(now, time))); readln; except on e: Exception do begin WriteLn(e.Message); readln; end; end; end.
    Mutasd a teljes hozzászólást!
  • Kiszúrta a szemem, ha tippelnem kéne az SSO miatt ugyan olyan gyors move nélkül is.
    Mutasd a teljes hozzászólást!
  • Még utoljára elgondolkodtam azon is, hogy nem csak a kisebbik kulcsszó file-ból csinálni gráfot, hanem a nagyobbik adat file-ból is. A kisebbik file gráfosítása csak 500x-osat gyorsított, a nagyobbiké még többet gyorsítana. De tényleg csak akkor érné meg, ha sokkal nagyobb lenne az a nagyobbik file, mert így a gráfosítása tovább tart, mint natúron végigkeresni, ergo időben sem éri meg. A memóriáról nem is beszélve. Csak tessék-lássék alapon a 0.3 megás file gráfja 300 mega lesz (a processz listában 319 megát írt vissza). 500x-os sebesség növekedés 1000x-es memóriáért cserébe. Így lamer-módjára indexelni talán egyszerű, de csak a sebességet látni az egészből nem biztos, hogy olyan jó buli. Ha megszűrném a karakter készletet, és 8 bites helyett inkább 1-2 bites indexelést használnék, és nem is teljes gráfot, hanem csak az első 3-4 karekterre indexelni, a többit meg listásan hagyni, biztos le lehetne szedni a memória növekedést max 2-3x-osig, és lévén akkor nem gyorsítana olyan sokat sem, talán érdemes lenne az adat file-t is gráfosítani. De persze ezek csak utólagos gondolatok.
    Mutasd a teljes hozzászólást!
  • Még tovább lehet optimalizálni :)
    Ha még teljesítményre lett volna szükség, akkor profilozás során előjött volna ez a 'bug' :)

    (Hogy világos legyen a probléma/BUG nem C++-osok számára.)
    MoveConstructor helyett CopyConstructor hívódott meg a 'const' miatt.
    A belső leírók másolása helyett deep-copy történik, ami nyilvánvalóan drágább művelet..

    Mérhetően nem lett gyorsabb a program a javítás után. (Bár most több minden fut a háttérbe)
    Azt is el tudom képzelni, hogy a fordító amúgy is kioptimalizálta a dolgot, magyarul nincs valós különbség, de most nincs időm megnézni, mikor mit fordít..

    ui:
    Kiszúrta a szemed, vagy más fordító warning-ol ilyen miatt?
    Mutasd a teljes hozzászólást!
  • for (const auto& key : istream_range<string>(file_keys)) { lu_first3[key].emplace_back( std::move(key)); }
    Mutasd a teljes hozzászólást!
  • Mókuskerék suxxx :D nekem is kene vagy bukom amit 2 hete szuttyogok :D
    Mutasd a teljes hozzászólást!
  • De nem biztos, hogy úgy a tényleg hatékony

    Ki kell probalni mindent!
    En ma kiprobaltam a clGetDeviceIDs functiont ugy, ahogy én szerettem volna, és nem ment ugy. Aztan kiprobaltam a 32millis kpe csobol osszerakott ereszemet, na az meg csodak csodajara mukodott még a slag vizmennyisegevel is :D
    Pedig hulyesegnek tunhet elsore...
    Mutasd a teljes hozzászólást!
  • Eredetileg én is több adatra gondoltam, de 2MB a korlát, amit ide fel lehet tölteni máshova meg nem akartam. Minden gépen futó egyforma txt-ket gerenáló scriptet meg nem tudok írni, így a kör bezárult.
    Most viszont visszatértem a hétköznapi mókuskerékbe, nincs időm tovább vinni a témát.

    Viszont mindenkinek köszönöm a játékot! 
    Mutasd a teljes hozzászólást!
  • Ahhoz, hogy mindent meg tudj találni első végigfutás alapján, X állapotgépet kell indítanod minden esetben, amikor egy index-kulcs kezdést érzékelsz. Én is azon filoztam még el az előző topicban, ha még megtalálod, ott elolvashatod. De nem biztos, hogy úgy a tényleg hatékony. Ha nagyon sok az index kulcs, akkor nem korlátos az, hány állapotgépet kell indítanod, és azok mind memória foglalás, memória init, utána felszabadítás, és az elvégzendő információ vizsgálat mennyisége nem kevesebb, mint ha ciklikusan keresnék ugyan abban a stringben újra és újra. Persze ti c-ben csináltátok, én c#-ben, így most nem tudjuk összehasonlítani a mindenféle eltérő optimalizálás miatt, de ha asm-ben lenne mindegyik példa, látható lenne a kódmennyiség alapján is, hogy a +1 mélységű ciklus hatékonyabb. És én olyan irányban próbáltam ki, hogy a kód felépítése hurcolható legyen, mert explicit és egyszerű adatkezelés mindenestül. Asm-re átvinni sem lenne túl nagy munka, ha később elő kell szednem. Egy valahonnét behúzott dll-t használni már nem hatékony olyan szempontból.

    A felvetett alap feladatban a sebesség dimenzióbeli különbsége egyébként csak annyi, hogy ha sebességet akarsz, indexeld a kulcs-szavakat. Az egy olyan optimalizálás, hogy memóriát használsz cpu idő helyett. Az dob kb 50000%-ot a sebességen. Aztán még szőrözhetsz további pár% sebességnyerésért, hogy még valamennyi memóriát használsz. De az már nem a nagyja. Maximum akkor lenne célja, ha valaki tényleg durva hardveren üzemeltetne ilyesmit, és a funkcionális teljesítmény / üzemeltetési költség kíméletlenül mérhető és számszerűsített hányadosát dörgölné a gyakorlat mindig az orra alá, hogy azon kellene javítani. Akkor, és neki tuti biztos érdekes lenne. De egy hétvégi játszadozás kedvéért a szélrózsa minden irányába elszaladni szerintem eddig tartott. A többi már nem funny.
    Mutasd a teljes hozzászólást!
  • "Egy 10 hosszú adaton végig futok 1-től 10-ig, aztán 2-től 10-ig, aztán 3-tól 10-ig és így tovább."
    Ahh igy mar vilagos!

    Te most akkor csinaltal egy hierarchikus keresest, a hierarchia pedig max(kulcs.size) melysegu.
    Mi 1 szintu hierarchiat csinaltunk az elso 3 karakter alapjan (ami utan hagyomanyos mosopor van).
    Az  Aho-Corasick  modszer viszont olyan graphot keszit, amelynek segitsegevel: Egy 10 hosszú adaton végig futok 1-től 10-ig es ezaltal minden talalat meg lett talalva.
    Mutasd a teljes hozzászólást!
  • A gráfban ott egy index marker is, és mindig minden adat-betűtől újra elkezdek végig vizsgálni. Egy 10 hosszú adaton végig futok 1-től 10-ig, aztán 2-től 10-ig, aztán 3-tól 10-ig és így tovább. Ha nincs olyan index, amilyen adat betűbe beleütköztem, akkor az a keresés abort, és következő lépés. Ergo nem biztos, hogy 2-től 10-ig vizsgálni fogom, lehetségesen csak 2-től 6-ig, és utána már indulok is újra 3-tól.

    Példa. Van egy olyan kulcsszód, "alma", meg egy olyan "lm". Beleakadsz egy ilyen adatba "palm". És elkezded feldolgozni. A "p" betűnél tovább lép, mert nincs olyan index kezdet. Következő adat-kezdőbetűre lép, ami az "a" lesz. Az "a" betűnél elindul létező indexen, de az adat "m" betűje után nem talált index markert, mert ahhoz kellene egy lezáró "a" is az adatban. Végigvizsgáltam, de feleslegesen. Van az úgy. Visszatér a keresés a következő adat-kezdőbetűhöz (és ezért fogja a kicsi részt megtalálni), indul az "l"-nél. Az "m" adatbetűnél megtalálja az index markert, ott van egy találat.

    De amúgy nem extrém nagy az a program, és direkt semmi implicit lib nincsen benne. Ha valahol zavart érzel az erőben, szaladj neki debuggal. Vagy csak adj be neki olyan adat és kulcs file-t, és nézd meg normál módon a találatok számát.
    Mutasd a teljes hozzászólást!
  • Javasolnám, hogy több legyen benne az adat és/vagy a szamitas.
    Csak mert most az i7 tulajdonosoknak tovább tölt be az exe, mint amig az dolgozik. 
    Mutasd a teljes hozzászólást!
  • Nem vilagos, hogy ket ilyen kulcsra ez mukodik-e:
    alma
    lm

    Ekkor ugye a root-bol felepitodik az 'alma', aztan szinten a root-bool felepitodik az 'lm'.
    Mikozben az 'alma' felepitogik az 'alm' részig, akkor mi lelez, hogy ott van már egy 'lm'?

    Tehát ha a word az, hogy:
    'palm', akkor ugye az alma gráfja beindul, de jelez-e az 'lm'?

    Ehhez az esethez szerintem rekuirzio kellene a keywordfile_index()-be mindenkeppen.

    (Na de már megint itt somfordálok, holott direkt azert keltem 6-kor (amibol lett fel 7), hogy melozzak. 
    Mutasd a teljes hozzászólást!
  • Én meg elkészültem a gráfos c# példával, amit @real_het lejjebb megpendített. A szópár egyezések kiszűrését nem raktam bele, mert igazából csak arra voltam kíváncsi, mennyire tud gyors lenni a módszer. Több szálra is át lehet rakni a koncepciót, de azt sem csináltam meg, mert lusta vagyok  

    A futása 1 szálon ment, egy 0.8 GHz-ig alulhúzott procin. C# fordító Microsoft.NET \ Framework64 \ v4.0.30319 (win7 ulti x64 sp1)

    A program kimenete:

    Adatfile beolvasasa: 138 millisec
    Kulcsszofile beolvasasa: 41 millisec
    Kulcsszofile indexelese: 1159 millisec
    Adatok keresese: 706 millisec
    Talalt egyezesek: 211130
    Enter..

    Forrás:

    namespace console { //----------program class start-------------------- public static class program { //--------------- public static System.Int64 prev_time; public static System.Byte[][] data_file; public static System.Byte[][] key_file; public static idxtag keys; public static System.Int32 data_pairs; //--------------- static public void report_time(System.String msg) { System.Int64 t1; //-- t1= System.DateTime.Now.Ticks / 10000; System.Console.WriteLine(msg+": "+(t1-program.prev_time).ToString()+" millisec"); program.prev_time= t1; //-- return;} //--------------- static public void datafile_read() { System.String[] t_file; System.Int32 i1; //-- t_file= System.IO.File.ReadAllLines("words_100K.txt"); program.data_file= new System.Byte[t_file.Length][]; for(i1=0; i1< t_file.Length; i1++) program.data_file[i1]= System.Text.Encoding.ASCII.GetBytes(t_file[i1]); //-- return;} //--------------- static public void keywordfile_read() { System.String[] t_file; System.Int32 i1; //-- t_file= System.IO.File.ReadAllLines("words_35K.txt"); program.key_file= new System.Byte[t_file.Length][]; for(i1=0; i1< t_file.Length; i1++) program.key_file[i1]= System.Text.Encoding.ASCII.GetBytes(t_file[i1]); //-- return;} //--------------- static public void keywordfile_index() { idxtag t_idx; System.Byte b1; System.Int32 i_row, i_col; //-- for(i_row= 0; i_row< program.key_file.Length; i_row++) { t_idx= program.keys; for(i_col= 0; i_col< program.key_file[i_row].Length; i_col++) { b1= program.key_file[i_row][i_col]; if (t_idx.table[b1]==null) t_idx.table[b1]= new idxtag(); t_idx= t_idx.table[b1]; continue;} t_idx.table[0]= t_idx; continue;} //-- return;} //--------------- static public void datafile_search() { idxtag t_idx, t_idx_end; System.Byte b1; System.Int32 i_row, i_col, i_col_sub; //-- for(i_row= 0; i_row< program.data_file.Length; i_row++) { for(i_col= 0; i_col< program.data_file[i_row].Length; i_col++) { t_idx= program.keys; for(i_col_sub= i_col; i_col_sub< program.data_file[i_row].Length; i_col_sub++) { b1= program.data_file[i_row][i_col_sub]; if (t_idx.table[b1]==null) break; t_idx= t_idx.table[b1]; t_idx_end= t_idx.table[0]; if (t_idx_end==null) continue; if (t_idx_end.Equals(t_idx)) program.data_pairs++; continue;} continue;} continue;} //-- return;} //--------------- static void Main(string[] args) { //-- program.prev_time= System.DateTime.Now.Ticks / 10000; program.keys= new idxtag(); program.data_pairs= 0; //-- program.datafile_read(); program.report_time("Adatfile beolvasasa"); //-- program.keywordfile_read(); program.report_time("Kulcsszofile beolvasasa"); program.keywordfile_index(); program.report_time("Kulcsszofile indexelese"); //-- program.datafile_search(); program.report_time("Adatok keresese"); System.Console.WriteLine("Talalt egyezesek: "+program.data_pairs.ToString()); //-- System.Console.WriteLine("Enter.."); System.Console.ReadLine(); return;} //--------------- } //-------program class end------------- //-------idxtag class start------------- public class idxtag { //--------------- public idxtag() { System.Int32 i1; //-- this.table= new idxtag[256]; for(i1=0; i1< 256; i1++) this.table[i1]= null; return; } //--------------- public idxtag[] table; //--------------- } //-------idxtag class end------------- }
    Mutasd a teljes hozzászólást!
  • Bár a 100 ms alatti futások után már a kutyát sem érdekli a T-SQL-em, de kipróbáltam és hát bejött :D

    Futási idő: 2537 ms
    Talált szópárok száma: 211092
    Forráskód:

    use Test go set nocount on; declare @time1 datetime = getutcdate() drop table if exists dbo.words_100K, dbo.words_35K, dbo.numbers, #tmp_result create table dbo.words_100K (word varchar(255) not null) create table dbo.words_35K (word varchar(255) not null ) create table dbo.numbers (id smallint not null primary key) BULK INSERT dbo.words_35K FROM 'd:\Letoltesek\Words\words_35K.txt' WITH (FIELDTERMINATOR ='', ROWTERMINATOR ='\n'); BULK INSERT dbo.words_100K FROM 'd:\Letoltesek\Words\words_100K.txt' WITH (FIELDTERMINATOR ='', ROWTERMINATOR ='\n'); insert into dbo.numbers (id) select top (30) row_number() over(order by (select null)) as id from sys.columns c1 cross join sys.columns c2 select distinct w100.word word_100K, w35.word as word_35K into #tmp_result from dbo.words_100K w100 cross join dbo.numbers n join dbo.words_35K w35 on w35.word = left(right(w100.word, n.id),len(w35.word)) and left(right(w100.word, n.id),3) = left(w35.word,3) where n.id <= len(w100.word) and n.id > 2 select @@rowcount as cnt_rows, datediff(ms, @time1, getutcdate()) as time
    Mutasd a teljes hozzászólást!
  • Kézzel 4 core-t erőltetve lassabb pár ms-al.

    A C++-os istream-es beolvasás volt még feltűnően lassú (~10ms extra) a D-s beolvasáshoz képest, úgyhogy azon még módosítottam. (egybe berántom a memóriába és egy tokenizer-el generálom a string_view-kat).

    Más gyors és egyszerű optimalizálási lehetőséget nem látok és teljesen elvagyok maradva a munkával :(

    Jelenlegi többszálú verzió (5 futtatás átlaga) 59.2 [ms].

    > words_2 Load - 17 [ms] Construct LookUp - 10 [ms] Search - 23 [ms] Count: 211130 Total - 59 [ms]
    Mutasd a teljes hozzászólást!
    Csatolt állomány
  • Egy keyword gráfos c# kódot éppen csiszolgatok, csak lusta vagyok, mint állat, és lassan készül 
    Mutasd a teljes hozzászólást!
  • Jaja, lazits, jovoheten lehet masik feladvany  jon 
    Mutasd a teljes hozzászólást!
  • Ezaz! És tuti lattam ezt az oldalt valaha :D

    Nalunk a 35K kulcs valoszinuleg olyan nagy graphot eredmenyezne, hogy az talan hatrany is lenne. (Rengeteg node, de 99.99%-us el sem lenne érve.)

    Na de jobb is, hogy nem rugozik ezen tovabb az agyam, mert volna mit OpenCL-ezni.
    Mutasd a teljes hozzászólást!
  • Ezen alapul az Aho-Corasick, ennek van GPU alapú implementációja is.
    Valószínűleg a gráf konstruálása sokkal lassabb, mint amennyi idő alatt végez az első 3 karakter alapján look-up-os megoldás viszont ha kész a gráf, onnantól..
    Ritkán változó kulcsok esetén ez az elképzelés lenne a nyerő.
    Mutasd a teljes hozzászólást!
  • 211130 -> Minden lehetseges match.

    Egy mas megkozelites (es ezt nyilvan mar kitalalltak, csak nem tudom, mi a neve):

    - A kereszoszavak alagjan kell generalni egy grafot.
    - minden graf pozicioban van egy lookup (ha tul sok a kulonbozo lehetoseg, ha keves, akkor egy lista), ami az eppen felgolgozott karakter alapjan egy uj graph pozicioba linkel. 
    - A graf node-okban pedig ha talalat van, akkor az is benne vagy egy listaban, amit lehet rakni a result-ba.

    A vegrehajtas rendkivul egyszeru. A graf felepitesenek meg nem is tudom, hogy hogy lehetne nekiallni ugy, hogy ne legyen nagysagrendekkel lassabb, mint a maga a 100K feldolgozasa :D
    Mutasd a teljes hozzászólást!
  • 151->75: duplája. Gondolom van ott 4 core is, de a 6MB cache kihasznalasahoz pont eleg 2 is, mivel 1 core csak 3-at lat.

    Irigylem az OpenMP-t amugy, mert azok meg tudtak oldani, hogy az ilyen 50ms-es feladatokra ne keruljon ra még 100ms overhead, mint a a Delphiben vagy most ahogy nézem D-ben is.

    Én még azt is feltételezem, hogy egyedul az openMP használja a Windows-bol azt a feature-t, amikor egy thread olyan sleep-be megy, amibol egy masik thread azt mikroszekundum alatt kepes felebreszteni, a tobbi meg messageket pollol vagy mittomen.
    Mutasd a teljes hozzászólást!
  • A találatok száma eltér a többiekétől. Direkt? :)
    Mutasd a teljes hozzászólást!
  • Köszönöm ma is tanultam valamit :)
    Mutasd a teljes hozzászólást!
  • És ha openmp segítségével engedünk egy kis párhuzamosítást is :)

    > words_1.exe Load - 28 [ms] Construct LookUp - 11 [ms] Search - 23 [ms] Count: 211130 Total - 75 [ms]
    kód - most újra előre beolvassuk az összes feldolgozandó elemet, hogy könnyeű legyen szétdobni a munkát, valamint hogy az omp-parallel működjön dobni kell a 'range-based for'-t és begin-end párost használni egy sima for loop-ban..

    // Search { MeasureTimeMs timer( "Search"); #pragma omp parallel for reduction(+: count) for ( auto it = words.cbegin(); it < words.cend(); ++it)
    Minden más változatlan..

    5 futtatás átlaga: 74.8 [ms]
    Azért már nagyon messze vagyunk az eredeti 7 órától :D
    Mutasd a teljes hozzászólást!
  • 5 futtatás átlaga 151.2 [ms] a javasolt módosítások után és még mindig biztosan lenne mit javítani..

    > words_0.exe Construct LookUp - 10 [ms] Search - 136 [ms] Count: 211130 Total - 152 [ms]
    Csatoltam a forrást.
    (-march=native-al opciót is hozzáadtam, bár előző verzió nem lett gyorsabb tőle, de így pl AVX2 készlet is elérhető)
    Mutasd a teljes hozzászólást!
    Csatolt állomány
  • Kiprobaltam ugy is, hogy az indexet shiftelem es csak a legalso 6bitet pakolom bele, de ez nem segitett, csak csunyabb lett a kod. A lookup lesz a bottleneck.

    foreach(t0; File(`words_100K.txt`).byLineCopy.map!stripRight){ int idx = ((t0[0]-32)<<tableSh) + (t0[1]-32); for(auto t = t0; t.length>=3; t = t[1..$]){ idx = ((idx<<tableSh)&(tableSize^^3-1)) + (t[2]-32); foreach(s; table[idx]){ if(t[3..$].startsWith(s[3..$])){ fout.writeln(s~": "~t0); cnt++; } } } }
    Mutasd a teljes hozzászólást!
  • Ebben még van tartalék: Legyen ez a hash calc ->

    enum tableSh = 6, tableSize = 1<<tableSh; int idxOf(const(char)* s){ return ((s[0]-32)<<(tableSh*2)) + ((s[1]-32)<<tableSh) + (s[2]-32); }
    Tehat a lookup csak 256K elemû, nem 16M elemû.
    Mutasd a teljes hozzászólást!
  • 176.6[ms] öt futtatás átlaga, ha lőre nem töltöm be vector-ba, hanem a search-ben használom az istream_range-t.

    Construct LookUp - 12 [ms] Search - 159 [ms] Count: 211130 Total - 175 [ms]

    forrás:

    int main() { MeasureTimeMs timer( "Total"); SpecialMap lu_first3(4 * 1024); size_t count = 0u; // Construct LookUp { MeasureTimeMs timer( "Construct LookUp"); ifstream file_keys("words_35K.txt"); for (const auto& key : istream_range<string>(file_keys)) { lu_first3[key].emplace_back( move(key)); } } // Search { MeasureTimeMs timer( "Search"); ifstream file_words("words_100K.txt"); for ( const auto& word : istream_range<string>(file_words)) { for (string_view sub = word; sub.size() >= 3u; sub = sub.substr(1) ) { if (auto it = lu_first3.find(sub); it != lu_first3.end()) { for ( const string& candidate : it->second ) { if ( starts_with(sub, candidate)) // c++20 has string_view::starts_with { ++count; } } } } } } // Results cout<<"Count: "<<count<<"\n"; return 0; }
    Mutasd a teljes hozzászólást!
abcd