View Full Version : [Tutti] Contest: T9 lookalike
Si vuole costruire una delle parti "Core" di un HID (Human Interface Device) che utilizza il T9
il concetto del T9 e' che, avendo una tastiera con pochi tasti, si vuole offrire all'utente la possibilita' di comporre in modo semplice tutte le parole possibili.
I tasti in questione sono 9 (in realta' per il nostro esercizio sono solo 8)
Con la seguente associazione statica e data a priori.
1 -> Nulla
2 -> abc
3 -> def
4 -> ghi
5 -> jkl
6 -> mno
7 -> prqs
8 -> tuv
9 -> wxyz
Si ha a dispozione un dizionario di parole dato, con tante parole, alcune corte, alcune lunghe, alcune lunghissime.
Lunghezza indefinita, ma volendo anche piu' lunghe di 50 caratteri, dato che si vuole a priori supportare anche lingue come il tedesco, con lunghezza indefinita delle parole, e magari anche qualche applicazione crittografica, dove le password possono appunto anche essere indefinitamente lunghe.
Si ottiene in ingresso un numero, es:
2426
Scopo dell'esercizio e' quello di restituire in output tutte le parole del nostro dizionario che possono essere ricondotte al numero in questione.
Supponendo in ingresso un dizionario/enciclopedia italiano, un output probabile potra' essere:
bico
ciao
cibo
cico
In modo ovviemente veloce, ovvero con possibilmente un algoritmo ottimale o quasi.
La soluzione deve essere semplicemente scalabile, nel senso che all'aumentare del numero di parole del dizionario la ricerca dell'output non deve peggiorare (troppo).
Un assunto che si puo' fare, ma che non deve essere vincolante, e' che ad un numero composto da tante cifre e' probabile che corrispondano meno parole reali, e viceversa, ma non e' detto che siano comunque per forza una sola.
Qui l'elenco delle parole italiane da supportare. Come detto, la lunghezza di una parola potrebbe essere a priori anche molto lunga.
http://www.yorku.ca/lbianchi/italian_words/italia-1a.zip
Aprite, leggete, capite e parsate come vi pare.
Presto arrivera' anche l'elenco dei valori numerici target di cui poi trovare le corrispondenze.
Aggiungerei anche che visto l'obiettivo del programma, non bisogna ottimizzare il caso della ricerca di "2426" ma più che altro la ricerca del nuovo gruppo dato il vecchio gruppo e la nuova cifra :stordita:
Ryuzaki_Eru
06-07-2010, 17:09
Questo è interessante :D
Ho tirato fuori questa schifezza in C++... però è limitato, perchè non tira fuori match parziali (bico, cico, nell'esempio) ma solo match completi.
Spero di vedere soluzioni più furbe della mia :D
edit: è un pò "convoluted", ma adesso dovrebbe stampare anche i match parziali...
Continuo a sperare in soluzioni migliori :D
martind@b0x:~/src/random/contest-t9$ cat > t9.cpp
#include <iostream>
#include <algorithm>
#include <iterator>
#include <map>
#include <string>
#include <fstream>
#include <sstream>
#include <set>
inline std::string int_to_string(int n) {
std::stringstream ss;
ss << n;
return ss.str();
}
struct t9bot {
std::map<char, std::string> keyboard;
std::multimap<std::string, std::string> candidates;
t9bot() {
const std::string chars[] = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
for (int i = 0; i < 8; ++i)
for (size_t j = 0; j < chars[i].length(); ++j)
keyboard[chars[i][j]] = int_to_string(i+2);
}
inline void operator()(const std::string word) {
std::string key;
for (size_t i = 0; i < word.length(); ++i) key += keyboard[word[i]];
candidates.insert(std::pair<std::string, std::string>(key, word));
}
void print_solutions(const std::string key) {
typedef std::multimap<std::string, std::string>::iterator map_iterator;
map_iterator low = candidates.lower_bound(key);
map_iterator high = candidates.upper_bound(key+"9");
std::set<std::string> solution_set;
for (map_iterator it = low; it != high; ++it)
solution_set.insert(it->second.substr(0, key.length()));
for (std::set<std::string>::iterator it = solution_set.begin();
it != solution_set.end(); ++it)
std::cout << *it << std::endl;
}
};
int main(int argc, char **argv) {
t9bot bot;
std::ifstream dictionary(argc > 1 ? argv[1] : "dictionary");
bot = std::for_each(
std::istream_iterator<std::string>(dictionary),
std::istream_iterator<std::string>(), bot);
while (std::cin.good()) {
std::string test;
std::cin >> test;
if (!test.empty()) bot.print_solutions(test);
}
return 0;
}
martind@b0x:~/src/random/contest-t9$ g++ -Wall -O2 t9.cpp -o t9
martind@b0x:~/src/random/contest-t9$ echo 2426 | ./t9 dict
agam
bian
bico
cham
chan
ciam
cian
ciao
cibo
cico
martind@b0x:~/src/random/contest-t9$
propongo un'idea per migliorare la versione che fa solo match completi: partendo dal dizionario é possibile creare una hash table dove le chiavi sono le sequenze numeriche necessarie per comporre le parole e i valori sono le liste delle parole che possono essere composte con una certa sequenza numerica; per esempio in questa hash table alla chiave 2426 sará contenuta una lista di due elementi, "cibo" e "ciao".
se N é il numero di parole del dizionario il tempo necessario per costruire questa hash table é O(N) e lo spazio anche (quindi, in particolare, lo spazio occupato resta asintoticamente identico). i vantaggi sono evidenti perché la hash table la si costruisce una volta per tutte e poi quando la si ha si puó fare qualunque consultazione in tempo costante, ottenendo grande efficienza anche nel caso in cui le cifre arrivino sul momento.
per completare l'idea non resta che pensare a un modo conveniente per memorizzare questa struttura dati in un file oltre che in memoria.
purtroppo é solo un'idea e non so se avró il tempo di realizzarla T_T
Lo stavo facendo ma poi m'è arrivata la licenza apple :asd:
Cmq stavo provando a realizzare un albero dove il nodo al N-esimo livello è la parola all'N-esima posizione.
Cmq stavo provando a realizzare un albero dove il nodo al N-esimo livello è la parola all'N-esima posizione. gli alberi in genere non contengono mica un solo nodo per livello... e comunque giá std::map é implementata tramite BST.
Ryuzaki_Eru
07-07-2010, 00:56
Lo stavo facendo ma poi m'è arrivata la licenza apple :asd:
What?:mbe: :D
DanieleC88
07-07-2010, 01:05
Conta solo il tempo di ricerca o anche il tempo di caricamento?
EDIT: e lo 0 lo possiamo ignorare?
EDIT: in più ci sono parole come "abat-jour" che non sono esclusivamente alfabetiche, le ignoriamo?
Lento a caricare ma veloce nella ricerca (più che altro veloce da scrivere :) )
dic=Hash.new
h=Hash.new
('a'..'r').inject(6) {|i,c| h[c.to_sym] = (i/3).to_i; i+=1;}
('s'..'y').inject(23) {|i,c| h[c.to_sym] = (i/3).to_i; i+=1;}
h[:z] = 9
#p h.inspect
File.open("merged.dic") do |f|
while line = f.gets
line.strip!
s = ""
line.split('').each do |c|
s+= h[c.to_sym].to_s
end
dic[s] ||= Array.new
dic[s] << line
end
# p dic.inspect
end
dic["2426"].each do |word|
puts word
end
dic["2777682666"].each do |word|
puts word
end
gli alberi in genere non contengono mica un solo nodo per livello... e comunque giá std::map é implementata tramite BST.
Stavo facendo un albero che per ogni livello contiene al più 26 sottoalberi, uno per ogni lettera dell'alfabeto.
Quindi se scrivi "2" lui ti ritorna i sottoalberi A, B e C e scrive a, b o c.
Quando poi scrivi "4" lui ritorna tutti i sottoalberi di A B C di senso compiuto (cioè, che non sono null) tra AG, AH, AI, BG, BH, BI, CG, CH, CI.
Una volta che la ricerca è terminata si ha un insieme di nodi; percorrendo i nodi verso l'alto si ottengono tutte le parole (anche incomplete) cercate.
In questo modo tra l'altro è possibile dare diversi pesi alle diverse parole, assegnando un peso ai nodi che compongono la parola...
banryu79
07-07-2010, 09:15
Lento a caricare ma veloce nella ricerca (più che altro veloce da scrivere :) )
Scusa, in che linguaggio è scritto? Non l'ho riconosciuto, sarà che stanotte ho dormito poco poco e adesso sono piegato :coffee:
@Tommo: bella l'idea dell'albero, ci avevo pensato anche io ieri, in parte proprio per il problema della distinzione tra parole formate/parole incomplete...
Scusa, in che linguaggio è scritto? Non l'ho riconosciuto, sarà che stanotte ho dormito poco poco e adesso sono piegato :coffee:
ruby, direi...
Comunque sono curioso di vedere una soluzione basta sull'idea postata da Tommo... avevo anch'io in mente qualcosa di simile ma non ci sono arrivato, e quindi ho ripiegato su una soluzione più barbara :(
Stavo facendo un albero che per ogni livello contiene al più 26 sottoalberi, uno per ogni lettera dell'alfabeto.
Quindi se scrivi "2" lui ti ritorna i sottoalberi A, B e C e scrive a, b o c.
Quando poi scrivi "4" lui ritorna tutti i sottoalberi di A B C di senso compiuto (cioè, che non sono null) tra AG, AH, AI, BG, BH, BI, CG, CH, CI.
Una volta che la ricerca è terminata si ha un insieme di nodi; percorrendo i nodi verso l'alto si ottengono tutte le parole (anche incomplete) cercate.
In questo modo tra l'altro è possibile dare diversi pesi alle diverse parole, assegnando un peso ai nodi che compongono la parola...
Quanto è grande un albero del genere che arriva fino a 50 di profondità ? 26^50 = 2^235 bit puntatori...ovvero è una soluzione improponibile ;)
Quanto è grande un albero del genere che arriva fino a 50 di profondità ? 26^50 = 2^235 bit puntatori...ovvero è una soluzione improponibile ;)
ma l'albero non e' completo, e contiene poche parole di quella lunghezza, per cui potrebbe essere fattibile. In ogni caso ci sono strutture dati apposite per questo scopo.
propongo un'idea per migliorare la versione che fa solo match completi: partendo dal dizionario é possibile creare una hash table dove le chiavi sono le sequenze numeriche necessarie per comporre le parole e i valori sono le liste delle parole che possono essere composte con una certa sequenza numerica; per esempio in questa hash table alla chiave 2426 sará contenuta una lista di due elementi, "cibo" e "ciao".
Si è quello che fa il mio programma. Sta tutto nella multimap.
wizard1993
07-07-2010, 10:41
posto la mia soluzione in java.
ho usato una metodologia simile a quella proposta da Tommo (è stata la prima cosa a cui ho pensato), solo invece di puntatori ho usato delle mappe.
Come diceva Cionci effettivamente usa una vagonata di memoria:
usando hashMap con fattore di caricamento 0.75 ho picchi di 300 mb di ram , usando mappe basate su alberi ne uso 200.
sul mio sistema la soluzione è elaborata (caricamento incluso) in 9 secondi
wizard1993@wizard1993-desktop:~/NetBeansProjects/t9/dist$ time java -jar t9.jar
[agam]
[bian]
[bico]
[cham]
[chan]
[ciam]
[cian]
[ciao]
[cibo]
[cico]
real 0m8.239s
user 0m9.621s
sys 0m0.420s
e il sorgente
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package t9;
import java.io.*;
import java.util.*;
/**
*
* @author wizard1993
*/
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) throws FileNotFoundException{
new T9Treee().search("2426");
//System.in.read();
}
}
class T9Treee {
node root = new node("");
final String symbols = "ABCDEFGHIJKLMNOPQRDQSTUVWXYZ";
HashMap<Integer, String> reverse = new HashMap<Integer, String>();
private void initTree() {
/*2 -> abc
3 -> def
4 -> ghi
5 -> jkl
6 -> mno
7 -> prqs
8 -> tuv
9 -> wxyz*/
for (int i = 0; i < symbols.length(); i++) {
String string = symbols.charAt(i) + "";
node n = new node(string);
root.nextNodes.put(string, n);
}
reverse.put(2, "abc");
reverse.put(3, "def");
reverse.put(4, "ghi");
reverse.put(5, "jkl");
reverse.put(6, "mno");
reverse.put(7, "pqrs");
reverse.put(8, "tuv");
reverse.put(9, "wxyz");
}
private void parse() throws FileNotFoundException {
for (int i = 0; i < symbols.length(); i++) {
String fileName = "ITALIANO." + symbols.charAt(i);
Scanner input = new Scanner(new BufferedInputStream(new FileInputStream(fileName)));
while (input.hasNext()) {
String string = input.nextLine();
insert(string);
}
input.close();
}
}
private void insert(String string) {
node n = root;
String swap = "";
for (int i = 0; i < string.length(); i++) {
String c = string.charAt(i) + "";
swap += c;
node next = n.nextNodes.get(c);
if (next == null) {
next = new node(c);
}
n.nextNodes.put(c, next);
next.words.add(swap);
n = next;
}
}
private class node {
String character;
public node(String character) {
this.character = character;
}
TreeMap<String, node> nextNodes = new TreeMap<String, T9Treee.node>();
Set<String> words = new TreeSet<String>();
}
public T9Treee() throws FileNotFoundException {
initTree();
parse();
}
public void search(String seq, node n, int depth) {
if(n==null)return;
if (depth >= seq.length() && n != null) {
System.out.println(n.words);
return;
}
String possible = reverse.get(Integer.valueOf(seq.charAt(depth) + ""));
for (int i = 0; i < possible.length(); i++) {
String c = possible.charAt(i) + "";
search(seq, n.nextNodes.get(c), depth+1);
}
}
public void search(String s){
search(s, root, 0);
}
}
ma l'albero non e' completo, e contiene poche parole di quella lunghezza, per cui potrebbe essere fattibile. In ogni caso ci sono strutture dati apposite per questo scopo.
Però se l'albero contiene le lettere 'a' e 'z' sei costretto a creare tutti i nodi null nel mezzo, con ovvio spreco di spazio ;)
Senza considerare che una indicizzazione completa non è necessaria.
ratman511
07-07-2010, 10:59
in che senso contiene nodi null nel mezzo?hanno detto che l'albero è composto da 26 sottoalberi e quindi le lettere dovrebbero esserci tutte.e l'indicizzazione completa perchè non è necessaria?
Si vuole costruire una delle parti "Core" di un HID (Human Interface Device) che utilizza il T9
il concetto del T9 e' che, avendo una tastiera con pochi tasti, si vuole offrire all'utente la possibilita' di comporre in modo semplice tutte le parole possibili.
I tasti in questione sono 9 (in realta' per il nostro esercizio sono solo 8)
Con la seguente associazione statica e data a priori.
1 -> Nulla
2 -> abc
3 -> def
4 -> ghi
5 -> jkl
6 -> mno
7 -> prqs
8 -> tuv
9 -> wxyz
Si ha a dispozione un dizionario di parole dato, con tante parole, alcune corte, alcune lunghe, alcune lunghissime.
Lunghezza indefinita, ma volendo anche piu' lunghe di 50 caratteri, dato che si vuole a priori supportare anche lingue come il tedesco, con lunghezza indefinita delle parole, e magari anche qualche applicazione crittografica, dove le password possono appunto anche essere indefinitamente lunghe.
Si ottiene in ingresso un numero, es:
2426
Scopo dell'esercizio e' quello di restituire in output tutte le parole del nostro dizionario che possono essere ricondotte al numero in questione.
Supponendo in ingresso un dizionario/enciclopedia italiano, un output probabile potra' essere:
bico
ciao
cibo
cico
In modo ovviemente veloce, ovvero con possibilmente un algoritmo ottimale o quasi.
La soluzione deve essere semplicemente scalabile, nel senso che all'aumentare del numero di parole del dizionario la ricerca dell'output non deve peggiorare (troppo).
Un assunto che si puo' fare, ma che non deve essere vincolante, e' che ad un numero composto da tante cifre e' probabile che corrispondano meno parole reali, e viceversa, ma non e' detto che siano comunque per forza una sola.
Qui l'elenco delle parole italiane da supportare. Come detto, la lunghezza di una parola potrebbe essere a priori anche molto lunga.
http://www.yorku.ca/lbianchi/italian_words/italia-1a.zip
Aprite, leggete, capite e parsate come vi pare.
Presto arrivera' anche l'elenco dei valori numerici target di cui poi trovare le corrispondenze.
Non mi e' chiaro se il risultato deve contenere solo le parole che corrispondono al codice o anche quelle che iniziano con quelle lettere.
In ogni caso, visto che non sono stati posti vincoli al consumo di memoria, propongo il mio che, una caricata la tabella, da la risposta in tempo istantaneo.
(Per passare dalal versione match completo o iniziale basta togliere/aggiungere il commento dove indicato)
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <map>
#include <sstream>
using namespace std;
vector<string> dict;
map<string,vector<const char*> > table;
int charButton[128] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 2, 2, 2, 3, 3,
3, 4, 4, 4, 5, 5, 5, 6, 6, 6,
7, 7, 7, 7, 8, 8, 8, 9, 9, 9,
9, 0, 0, 0, 0, 0, 0, 2, 2, 2,
3, 3, 3, 4, 4, 4, 5, 5, 5, 6,
6, 6, 7, 7, 7, 7, 8, 8, 8, 9,
9, 9, 9, 0, 0, 0, 0, 0 };
void loadDictionary(vector<string>& dict, const char* filename )
{
ifstream in(filename);
string s;
while( in >> s )
{
dict.push_back(s);
}
}
int stringToKey( const std::string& s )
{
int result=0;
for ( int i=0 ; i < s.size(); ++i )
{
result = result*10 + charButton[s[i]];
// commentare la seguente per la versione solo parole complete
ostringstream out;
out << result;
table[out.str()].push_back(s.c_str());
}
return result;
}
void prepareLookupTable( const vector<string>& dict, map<string,vector<const char*> >& table )
{
for ( unsigned int i=0 ; i<dict.size() ; ++i )
{
int key = stringToKey(dict[i]);
// versione solo con parole complete
// table[key].push_back( dict[i].c_str() );
}
}
int main(int argc,char** argv)
{
loadDictionary(dict,argv[1]);
prepareLookupTable( dict, table );
string num;
while ( cin >> num )
{
for ( int i=0 ; i<table[num].size(); ++i )
{
cout << table[num][i] << ' ';
}
cout << endl;
}
}
Ryuzaki_Eru
07-07-2010, 15:08
Ecco una versione Python. Come vedrete voi stessi il codice fa letteralmente ca***e, ma l'ho scritto mentre preparavo la valigia e ora devo andare a mangiare. Ha *ampissimi* margini di miglioramento; in tarda serata lo sistemo per bene.
from collections import defaultdict
from string import ascii_lowercase
import sys
diz_base = {}
diz_finale = defaultdict(list)
pos = ""
codice = sys.argv[1]
for i, c in enumerate(ascii_lowercase):
if c in ["t", "u"]:
diz_base[c] = (i/3) + 2
if c in ["s", "v", "y", "z"]:
diz_base[c] = (i/3) + 1
else:
diz_base[c] = (i/3) + 2
for parola in open("merged"):
for carattere in parola:
if carattere not in ["\n", "-", "\r"]:
pos += str(diz_base[carattere])
if pos == codice:
if parola[:len(codice)] not in diz_finale[pos]:
diz_finale[pos].append(parola[:len(codice)])
pos = ""
continue
diz_finale[pos].append(parola)
pos = ""
print "\n".join(diz_finale[codice])
Scusa, in che linguaggio è scritto? Non l'ho riconosciuto, sarà che stanotte ho dormito poco poco e adesso sono piegato :coffee:
@Tommo: bella l'idea dell'albero, ci avevo pensato anche io ieri, in parte proprio per il problema della distinzione tra parole formate/parole incomplete...
ruby! :)
L'ho riscritto in C usando una perfect hashing function con la lib cmph
rikiji ~/code/dic $ time ./hfind
key: 2426, word: ciao
key: 2426, word: cibo
key: 2222333, word: accadde
key: 32543, word: dalie
real 0m0.011s
user 0m0.004s
sys 0m0.008s
rikiji ~/code/dic $ time ./hfind 84462
key: 84462, word: tigna
key: 84462, word: vigna
real 0m0.010s
user 0m0.004s
sys 0m0.004s
rikiji ~/code/dic $
Sta un po' a compilare e l'eseguibile è di 13.6 MB :D ma è VELOCE!
Source ed eseguibile qui (http://rikiji.it/data/dichash.tar.gz), serve libcmph0
Se interessa impacchetto anche il source usato per creare l'hash (CHM)
In ogni caso, visto che non sono stati posti vincoli al consumo di memoria, propongo il mio che, una caricata la tabella, da la risposta in tempo istantaneo. credo che tu abbia realizzato la mia idea :p
edit - non ti preoccupare per il consumo di memoria, leggi il mio post precedente in cui ho fatto un'analisi della complessitá spaziale: a meno che non mi sbaglio resta sempre O(N) perché la hash map contiene ciascuna parola al piu una volta, quindi asintoticamente non peggiora (anche il dizionario originale occupa spazio lineare nel numero di parole ovviamente).
Il mio algoritmo ha un tempo di costruzione dell'indice indicativamente (non è proprio così perché nella realtà perché si semplifica molto) pari a O(N). Con N il numero di caratteri presenti nel dizionario.
Il tempo di ricerca è O(M) con M pari al numero di cifre da ricercare.
Il tempo di recupero delle sequenze di parole che soddisfano la ricerca è pari a O(K) con K il numero di parole che soddisfano al ricerca (e di conseguenza il numero di lettere che le compongono).
In pratica il termine O(K) sarà predominante su O(M) nella maggior parte dei casi. Nel caso in cui si recupera una parola singola O(M) darò lo stesso contributo di O(K).
Quindi di fatto la complessità di ricerca è pari al tempo necessario a leggere i match dal dizionario ;)
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <cstring>
using namespace std;
int toNumber(char c)
{
static int map[] = {0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,7,7,7,7};
c = tolower(c);
if(c >= 'a' && c <= 'z')
return map[(int)(c - 'a')];
return -1;
}
struct Matching
{
int start;
int lenght;
streampos pos;
};
class Node
{
Node ** childs;
list<Matching> mList;
int child_count;
public:
Node():childs(NULL), child_count(0)
{
}
bool hasChild(const int index) const
{
if(!childs)
return false;
if(!childs[index])
return false;
return true;
}
Node * getChild(const int index)
{
return childs[index];
}
void updateMatching(const int word_index, streampos file_pos)
{
if(mList.size() > 0)
{
Matching &m = mList.back();
if(m.start + m.lenght == word_index)
{
m.lenght++;
return;
}
}
Matching m = {word_index, 1, file_pos};
mList.push_back(m);
}
Node * updateNode(const int index, const int word_index, streampos file_pos)
{
if(!childs)
{
childs = new Node * [8];
memset(childs, 0, 8 * sizeof(Node *));
}
if(!childs[index])
{
childs[index] = new Node();
child_count++;
}
updateMatching(word_index, file_pos);
return childs[index];
}
list<Matching> & getMatchings()
{
return mList;
}
~Node()
{
if(childs)
delete[] childs;
}
};
class T9Tree
{
Node * root;
const string dictionary;
void addWord(const string word, const int word_index, const int unique_pos, const streampos file_pos)
{
Node * node = root;
for(int i = 0; i < unique_pos; ++i)
{
int number = toNumber(word.at(i));
if(number >= 0)
node = node->updateNode(number, word_index, file_pos);
}
node->updateMatching(word_index, file_pos);
}
int compareTwo(string & ref, string & word)
{
unsigned int pos = 0;
while(ref.size() > pos && word.size() > pos && ref.at(pos) == word.at(pos))
{
++pos;
}
return pos;
}
int compareThree(string & ref1, string & word, string & ref2)
{
unsigned int pos = 0;
bool flag = true, flag1 = true, flag2 = true;
while(flag)
{
flag1 = flag1 && pos < ref1.size() && ref1.at(pos) == word.at(pos);
flag2 = flag2 && pos < ref2.size() && ref2.at(pos) == word.at(pos);
++pos;
flag = (flag1 || flag2) && word.size() > pos;
}
return pos;
}
public:
T9Tree(const string fileName): dictionary(fileName)
{
root = new Node();
}
bool parseDictionary()
{
ifstream f(dictionary.c_str());
if(!f.is_open())
return false;
string previous;
string word;
string next;
//add first word
getline(f, previous);
streampos curr_file_pos = f.tellg();
getline(f, word);
streampos next_file_pos;
int unique = compareTwo(word, previous);
addWord(previous, 0, unique, 0);
int word_index = 0;
while(1)
{
word_index++;
next_file_pos = f.tellg();
getline(f, next);
if(f.eof())
break;
if(next.size())
{
unique = compareThree(previous, word, next);
addWord(word, word_index, unique, curr_file_pos);
previous = word;
word = next;
curr_file_pos = next_file_pos;
}
}
//add last word
unique = compareTwo(previous, word);
addWord(word, word_index, unique, curr_file_pos);
f.close();
return true;
}
bool find(const string number, vector<string> &result)
{
ifstream f(dictionary.c_str());
if(!f.is_open())
return false;
Node * node = root;
for(unsigned int i = 0; i < number.size(); ++i)
{
int index = number.at(i) - '2';
if(node->hasChild(index))
node = node->getChild(index);
else
{
f.close();
return false;
}
}
list<Matching> &l = node->getMatchings();
for(list<Matching>::iterator it = l.begin(); it != l.end(); it++)
{
Matching &m = *it;
cout << "Offset: "<< m.pos << " Start index: " << m.start << " Lenght: " << m.lenght << endl;
f.seekg(m.pos, ios_base::beg);
for(int i = 0; i < m.lenght; i++)
{
string s;
getline(f, s);
result.push_back(s);
}
}
f.close();
return true;
}
~T9Tree()
{
delete root;
}
};
int main(int argc, char *argv[])
{
T9Tree t9("italiano.txt");
t9.parseDictionary();
vector<string> v;
if(!t9.find(argv[1], v))
{
cout << "Corrispondenza non trovata" << endl;
}
else
{
for(vector<string>::iterator it = v.begin(); it != v.end(); it++)
{
cout << *it << endl;
}
}
return 0;
}
I numeri vanno passati da riga di comando. Ocio che non ci sono controlli sui numeri passati, quindi bisogna inserire solo numeri da 2 a 9 ;)
Il file del dizionario da usare è questo: http://www.mediafire.com/?5unlytjj3ni
L'albero è formato da nodi contenti 8 puntatori a sotto nodi.
Si naviga nell'albero, se dovessimo cercare "234", con radice[2]->nodo[3]->nodo[4].
All'interno dell'albero c'è una lista in cui ogni elemento indica una sequenza di parole che soddisfano i numeri necessari per arrivare a quel nodo dell'albero. La sequenza è identificata da {offset nel file, indice della prima parola, lunghezza della sequenza} (volendo si può eliminare il conteggio delle parole ed inserire solo offset di inizio ed offset di fine ;)). Ogni sequenza è ovviamente formata da parole consecutive nel file ;)
Dicevo appunto che è inutile indicizzare tutte le lettere delle parole perché per ogni parola ci si può fermare esattamente al punto in cui questa parola non ha in comune altre lettere con la parola precedente e la parola successiva.
Quindi avendo:
abbondante
abbondantemente <--- da indicizzare
abbondanti
Basta indicizzare fino alla "m", in modo da identificare univocamente la parola. Ecco perché la complessità dell'indicizzazione è addirittura minore della complessità di lettura del dizionario.
Di conseguenza scala benissimo all'aumentare della lunghezza delle parole.
La memoria occupata è di 46.5 MB sul mio sistema a 64 bit. Come ho scritto sopra si può fare di meglio utilizzando solo due campi nelle sequenze.
Il tempo di indicizzazione è di circa 1 secondo su un Core 2 Duo a 2.13 GHz.
Sta un po' a compilare e l'eseguibile è di 13.6 MB :D ma è VELOCE!
Source ed eseguibile qui (http://rikiji.it/data/dichash.tar.gz), serve libcmph0
Se interessa impacchetto anche il source usato per creare l'hash (CHM)
Hai già creato l'hash, così non vale :cry:
Comunque io per 2426 ho questo output:
agamia
agamica
agamiche
agamici
agamico
agamie
bianca
biancastra
biancastre
biancastri
biancastro
bianche
biancheggia
biancheggiare
biancheggiava
biancheria
biancherie
biancherista
biancheriste
biancheristi
bianchetta
bianchette
bianchetti
bianchetto
bianchezza
bianchezze
bianchi
bianchicce
bianchicci
bianchiccia
bianchiccio
bianchimenti
bianchimento
bianchini
bianco
biancone
bianconi
biancore
biancori
biancospini
biancospino
biancostati
biancostato
biancovestito
bicocca
bicocche
bicolore
bicolori
biconcava
biconcave
biconcavi
biconcavo
biconvessa
biconvesse
biconvessi
biconvesso
bicorna
bicorne
bicorni
bicornia
bicornie
bicorno
champagne
champagnes
chance
chances
chansonnier
chansonniers
chantant
chanteuse
chanteuses
chantilly
ciambella
ciambellani
ciambellano
ciambelle
ciana
cianammide
cianammidi
cianca
ciance
cianche
ciancia
cianciafruscola
cianciafruscole
cianciando
cianciare
ciancioni
ciane
cianfrusaglia
cianfrusaglie
ciangottii
ciangottio
ciani
cianica
cianiche
cianici
cianico
cianidrica
cianidriche
cianidrici
cianidrico
ciano
cianogeni
cianogeno
cianografi
cianografia
cianografica
cianografiche
cianografici
cianografico
cianografie
cianografo
cianosi
cianotica
cianotiche
cianotici
cianotico
cianurazione
cianurazioni
cianuri
cianuro
ciao
cibo
cibori
ciborio
cicogna
cicogne
cicoria
cicorie
Cioè fa il match su tutte le parole, anche più lunghe... Avevo capito che andasse realizzato così :(
Ryuzaki_Eru
07-07-2010, 15:46
Eh no, è proprio come il cel: dà il match su tutte le parole con quel codice, al massimo può suggerire le altre parole, ma il match avviene sempre con il codice che usi ;)
Quanto ti ci mette a creare l'hash ?
Hai già creato l'hash, così non vale :cry:
Cioè fa il match su tutte le parole, anche più lunghe... Avevo capito che andasse realizzato così :(
Ora bencho creando l'hash al volo! :oink:
La tua soluzione è decisamente più flessibile! :)
Eh no, è proprio come il cel: dà il match su tutte le parole con quel codice, al massimo può suggerire le altre parole, ma il match avviene sempre con il codice che usi ;)
Ora bencho creando l'hash al volo! :oink:
La tua soluzione è decisamente più flessibile! :)
Inserendo 22266326836 cosa ottenete ?
rikiji ~/code/dic $ time ./hcreatefind
key:2222333 -- hash:accadde
real 0m0.248s
user 0m0.240s
sys 0m0.008s
http://rikiji.it/data/tb-moar.gif (http://rikiji.it/data/moar.gif)
questo è il call graph, a sinistra cmph_search cerca le entry, il resto crea l'hash. Sta comunque poco perchè il lavoro è spostato a tempo di compilazione nel cercare la funzione di hashing corretta...
Ti posterei il source ma sono 16MB perchè ho incluso il dizionario nel sorgente :(
Notare 4.3% buttato a fare strlen :ciapet:
Inserendo 22266326836 cosa ottenete ?
not found... cioè se mettessi un controllo mi direbbe not found :D
not found... cioè se mettessi un controllo mi direbbe not found :D
Funzionalmente è paragonabile a quando il T9 si blocca e non ti fa inserire altre lettere, no ?
Invece quella sequenza matcha parzialmente una parola del vocabolario, quindi non si dovrebbe fermare...
DanieleC88
07-07-2010, 16:25
Io ottengo "abbondantem".
Funzionalmente è paragonabile a quando il T9 si blocca e non ti fa inserire altre lettere, no ?
Invece quella sequenza matcha parzialmente una parola del vocabolario, quindi non si dovrebbe fermare...
MM così sì... appena ho un po' di tempo cambio la gestione delle previsioni che è direttamente collegata a questo
Ryuzaki_Eru
07-07-2010, 16:41
Inserendo 22266326836 cosa ottenete ?
"Abbondantem".
DanieleC88
07-07-2010, 17:20
Visto che ormai ci siamo, posto anche la mia. È la seconda soluzione che sviluppo, la prima utilizzava (malissimo) un albero: con vagonate di memoria e tempi di caricamento enormi, era rapidissimo nella ricerca. Quest'altro usa decisamente meno memoria, e non riesco a farlo andare oltre i 500 millisecondi, compreso il tempo di caricamento dei dati. Purtroppo non ho Psyco installato al momento, altrimenti penso che sarebbe ancora più veloce. :)
L'idea è semplicissima, ed il codice anche.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
try:
import psyco
psyco.full()
except:
print " [**] Going on without Psyco!"
print
import string
import sys
chars = {
'a': 2, 'b': 2, 'c': 2,
'd': 3, 'e': 3, 'f': 3,
'g': 4, 'h': 4, 'i': 4,
'j': 5, 'k': 5, 'l': 5,
'm': 6, 'n': 6, 'o': 6,
'p': 7, 'q': 7, 'r': 7, 's': 7,
't': 8, 'u': 8, 'v': 8,
'w': 9, 'x': 9, 'y': 9, 'z': 9
}
def readFile(fileName, dictionary):
f = open(fileName)
for token in f:
dictionary.append(token.strip())
f.close()
def isCompatible(word, sequence):
if len(word) < len(sequence):
return False
for i in range(len(sequence)):
if chars[word[i]] != int(sequence[i]):
return False
return True
if __name__ == "__main__":
letters = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
dictionary = [[] for i in range(9)]
print " [--] Loading data..."
for i in range(len(letters)):
for j in letters[i]:
fileName = '.'.join(["ITALIANO", j.upper()])
readFile(fileName, dictionary[i+1])
print " [--] Done."
print
h = set()
for arg in sys.argv[1:]:
i = int(arg[0])
n = len(arg)
for word in dictionary[i-1]:
if isCompatible(word, arg):
h.add(word[:n])
print
for word in h:
print word
sys.exit(0)
Ho abbandonato l'indicizzazione parziale e ridotto l'uso della memoria.
Ora dovrebbe tornare tutto come il testo di Gugo ;)
Il file del dizionario: http://www.mediafire.com/?5unlytjj3ni
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <cstring>
using namespace std;
int toNumber(char c)
{
static int map[] = {0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,7,7,7,7};
c = tolower(c);
if(c >= 'a' && c <= 'z')
return map[(int)(c - 'a')];
return -1;
}
class Node
{
Node ** childs;
list<streampos> mList;
public:
Node():childs(NULL)
{
}
bool hasChild(const int index) const
{
if(!childs)
return false;
if(!childs[index])
return false;
return true;
}
Node * getChild(const int index)
{
return childs[index];
}
void updateMatching(const streampos file_pos)
{
mList.push_back(file_pos);
}
Node * updateNode(const int index, const streampos file_pos, const bool skip_matching)
{
if(!childs)
{
childs = new Node * [8];
memset(childs, 0, 8 * sizeof(Node *));
}
if(!childs[index])
{
childs[index] = new Node();
}
if(!skip_matching)
updateMatching(file_pos);
return childs[index];
}
list<streampos> & getMatchings()
{
return mList;
}
~Node()
{
if(childs)
delete[] childs;
}
};
class T9Tree
{
Node * root;
const string dictionary;
string prev_word;
void addWord(const string word, const streampos file_pos)
{
Node * node = root;
bool flag = true;
for(unsigned int i = 0; i < word.size(); ++i)
{
int number = toNumber(word.at(i));
if(number >= 0)
node = node->updateNode(number, file_pos, flag);
flag = flag && prev_word.size() > i && prev_word.at(i) == word.at(i);
}
if(!flag)
node->updateMatching(file_pos);
prev_word = word;
}
public:
T9Tree(const string fileName): dictionary(fileName), prev_word("")
{
root = new Node();
}
bool parseDictionary()
{
ifstream f(dictionary.c_str());
if(!f.is_open())
return false;
string word;
streampos file_pos;
while(1)
{
file_pos = f.tellg();
getline(f, word);
if(f.eof())
break;
if(word.size())
{
addWord(word, file_pos);
}
}
f.close();
return true;
}
bool find(const string numbers, vector<string> &result)
{
Node * node = root;
for(unsigned int i = 0; i < numbers.size(); ++i)
{
int index = numbers.at(i) - '2';
if(node->hasChild(index))
node = node->getChild(index);
else
{
return false;
}
}
ifstream f(dictionary.c_str());
if(!f.is_open())
return false;
list<streampos> &l = node->getMatchings();
for(list<streampos>::iterator it = l.begin(); it != l.end(); it++)
{
streampos &pos = *it;
cout << "Offset: " << pos << endl;
f.seekg(pos, ios_base::beg);
string s;
getline(f, s);
result.push_back(s.substr(0, numbers.size()));
}
f.close();
return true;
}
~T9Tree()
{
delete root;
}
};
int main(int argc, char *argv[])
{
T9Tree t9("italiano.txt");
t9.parseDictionary();
vector<string> v;
if(!t9.find(argv[1], v))
{
cout << "Corrispondenza non trovata" << endl;
}
else
{
for(vector<string>::iterator it = v.begin(); it != v.end(); it++)
{
cout << *it << endl;
}
}
return 0;
}
Daniele...in pratica ti scorri il dizionario ? Però in un run carichi solo la parte del dizionario che ti serve... Mi pare logico che debba funzionare anche per qualsiasi numero si trovi in prima paosizione...visto che Gugo darà una lista di numeri da verificare ;)
rikiji ~/code/dic $ time ./hcreatefind
key:2222333 -- hash:accadde
real 0m0.248s
user 0m0.240s
sys 0m0.008s
http://rikiji.it/data/tb-moar.gif (http://rikiji.it/data/moar.gif)
questo è il call graph, a sinistra cmph_search cerca le entry, il resto crea l'hash. Sta comunque poco perchè il lavoro è spostato a tempo di compilazione nel cercare la funzione di hashing corretta...
Ti posterei il source ma sono 16MB perchè ho incluso il dizionario nel sorgente :(
Notare 4.3% buttato a fare strlen :ciapet:
Come l'hai creato il grafico?
DanieleC88
07-07-2010, 17:37
Semplicemente ho deciso di caricare tutto il dizionario (spezzettato in base ai gruppi di lettere) e poi di esaminare solo le parole appartenenti al gruppo di lettere che mi interessa. Ora l'ho sviluppato per funzionare con una parola singola perché quella mi interessava, se sarà una lista di parole dovrò cambiare poco. Lo faccio ora. :D
Semplicemente ho deciso di caricare tutto il dizionario (spezzettato in base ai gruppi di lettere) e poi di esaminare solo le parole appartenenti al gruppo di lettere che mi interessa. Ora l'ho sviluppato per funzionare con una parola singola perché quella mi interessava, se sarà una lista di parole dovrò cambiare poco. Lo faccio ora. :D
Ma i tempi di caricamento sono 10 volte maggiori ;)
DanieleC88
07-07-2010, 17:47
Non ho capito... io il dizionario lo carico una sola volta. Poi, per ogni sequenza numerica ne prendo solo il pezzo che mi interessa. Ma in memoria c'è sempre l'intero dizionario. :)
EDIT: aggiornato nel vecchio post per supportare un numero indefinito di sequenze numeriche in input. Funziona se l'ordinamento dei risultati non è rilevante.
Ryuzaki_Eru
07-07-2010, 18:28
Casomai per renderlo rilevante basta una piccolissima modifica :)
Non ho capito... io il dizionario lo carico una sola volta. Poi, per ogni sequenza numerica ne prendo solo il pezzo che mi interessa. Ma in memoria c'è sempre l'intero dizionario. :)
Ho letto male il sorgente :D
Ryuzaki_Eru
07-07-2010, 18:45
Effetti secondari del lavorare troppo con C/C++ :D
Ho abbandonato l'indicizzazione parziale e ridotto l'uso della memoria.
Ora dovrebbe tornare tutto come il testo di Gugo ;)
Il file del dizionario: http://www.mediafire.com/?5unlytjj3ni
Ho aggiunto nuovamente l'indicizzazione parziale, in questo modo scala molto meglio con le parole lunghe (oltre a circa il 30% meno di ram consumata) con le stesse prestazioni.
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <cstring>
using namespace std;
int toNumber(char c)
{
static int map[] = {0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,7,7,7,7};
c = tolower(c);
if(c >= 'a' && c <= 'z')
return map[(int)(c - 'a')];
return -1;
}
char toNumberChar(char c)
{
return '2' + toNumber(c);
}
class Node
{
Node ** children;
list<streampos> mList;
public:
Node():children(NULL)
{
}
bool hasChildren()
{
return children != 0;
}
bool hasChild(const int index) const
{
if(!children)
return false;
if(!children[index])
return false;
return true;
}
Node * getChild(const int index)
{
return children[index];
}
void updateMatching(const streampos file_pos)
{
mList.push_back(file_pos);
}
Node * updateNode(const int index, const streampos file_pos, const bool skip_matching)
{
if(!children)
{
children = new Node * [8];
memset(children, 0, 8 * sizeof(Node *));
}
if(!children[index])
{
children[index] = new Node();
}
if(!skip_matching)
updateMatching(file_pos);
return children[index];
}
list<streampos> & getMatchings()
{
return mList;
}
~Node()
{
if(children)
delete[] children;
}
};
class T9Tree
{
Node * root;
const string dictionary;
string prev_word;
void addWord(const string word, const unsigned int unique, const streampos file_pos)
{
Node * node = root;
bool flag = true;
if(word == "abbondantemente")
flag = true;
for(unsigned int i = 0; i < unique; ++i)
{
int number = toNumber(word.at(i));
if(number >= 0)
node = node->updateNode(number, file_pos, flag);
flag = flag && prev_word.size() > i && prev_word.at(i) == word.at(i);
}
if(!flag)
node->updateMatching(file_pos);
prev_word = word;
}
int compareTwo(string & ref, string & word)
{
unsigned int pos = 0;
while(ref.size() > pos && word.size() > pos && ref.at(pos) == word.at(pos))
{
++pos;
}
return pos;
}
int compareThree(string & ref1, string & word, string & ref2)
{
unsigned int pos = 0;
bool flag = true, flag1 = true, flag2 = true;
while(flag)
{
flag1 = flag1 && pos < ref1.size() && ref1.at(pos) == word.at(pos);
flag2 = flag2 && pos < ref2.size() && ref2.at(pos) == word.at(pos);
++pos;
flag = (flag1 || flag2) && word.size() > pos;
}
return pos;
}
public:
T9Tree(const string fileName): dictionary(fileName), prev_word("")
{
root = new Node();
}
bool parseDictionary()
{
ifstream f(dictionary.c_str());
if(!f.is_open())
return false;
string previous;
string word;
string next;
//add first word
getline(f, previous);
streampos curr_file_pos = f.tellg();
getline(f, word);
streampos next_file_pos;
int unique = compareTwo(word, previous);
addWord(previous, unique, 0);
int word_index = 0;
while(1)
{
word_index++;
next_file_pos = f.tellg();
getline(f, next);
if(f.eof())
break;
if(next.size())
{
unique = compareThree(previous, word, next);
addWord(word, unique, curr_file_pos);
previous = word;
word = next;
curr_file_pos = next_file_pos;
}
}
//add last word
unique = compareTwo(previous, word);
addWord(word, unique, curr_file_pos);
f.close();
return true;
}
bool find(const string numbers, vector<string> &result)
{
Node * node = root;
bool mustVerify = false;
int verifyIndex = 0;
for(unsigned int i = 0; i < numbers.size(); ++i)
{
int index = numbers.at(i) - '2';
if(node->hasChild(index))
node = node->getChild(index);
else
{
if(node->hasChildren())
return false;
else
{
mustVerify = true;
verifyIndex = i;
break;
}
}
}
ifstream f(dictionary.c_str());
if(!f.is_open())
return false;
list<streampos> &l = node->getMatchings();
for(list<streampos>::iterator it = l.begin(); it != l.end(); it++)
{
streampos &pos = *it;
//cout << "Offset: " << pos << endl;
f.seekg(pos, ios_base::beg);
string s;
getline(f, s);
bool verified = true;
if(mustVerify && s.size() >= numbers.size())
{
for(unsigned int i = verifyIndex; i < numbers.size(); ++i)
{
if(toNumberChar(s.at(i)) != numbers.at(i))
{
verified = false;
break;
}
}
}
if(verified)
result.push_back(s.substr(0, numbers.size()));
}
f.close();
return result.size() > 0;
}
~T9Tree()
{
delete root;
}
};
void find(T9Tree &t9, const string numbers)
{
cout << "Find " << numbers << ":" << endl;
vector<string> v;
if(!t9.find(numbers, v))
{
cout << "Corrispondenza non trovata" << endl;
}
else
{
for(vector<string>::iterator it = v.begin(); it != v.end(); it++)
{
cout << *it << endl;
}
}
}
int main(int argc, char *argv[])
{
T9Tree t9("italiano.txt");
t9.parseDictionary();
find(t9, argv[1]);
return 0;
}
shainer_dev
07-07-2010, 21:01
Tento una mia soluzione in Python!
Sembra funzionare perfettamente, per il numero 2426 time mi riporta come tempo di esecuzione reale 4.8 secondi. Non so dire molto sulla sua efficienza in generale, sicuramente è possibile pensare a qualche ottimizzazione e la stampa finale avrebbe bisogno di una ritoccatina "grafica".
Il codice lo trovate qui (http://pastebin.com/bwWsL3EX).
Lisa
Come l'hai creato il grafico?
con gli strumenti di profiling di google
http://code.google.com/p/google-perftools/
DanieleC88
07-07-2010, 22:09
[...]
Però... "childs" non si può leggere! Si dice "children"! :D
Però... "childs" non si può leggere! Si dice "children"! :D
Che figura :D
Ryuzaki_Eru
08-07-2010, 00:16
Però... "childs" non si può leggere! Si dice "children"! :D
Mi ricorda il libro di Algebra :D
Allora l'idea che mi è venuta è in pratica quella di costruire una specie di automa a stati finiti in cui ogni nodo contiene una lista di parole associate alla sequenza in input.
Ogni nodo contiene anche una mappa delle transizioni del tipo {Numero} -> {Nodo}.
Questo è il codice in Python di base, non è il massimo ma è da poco che scrivo in Python:
class Node:
def __init__(self):
self.table = dict()
self.wordlist = []
def add(self, word):
self.wordlist.append(word)
def get(self, num):
return self.table.get(num)
def set(self, num, node):
self.table[num] = node
return node
start = Node()
keyboard = { 'a':'2', 'b':'2', 'c':'2',
'd':'3', 'e':'3', 'f':'3',
'g':'4', 'h':'4', 'i':'4',
'j':'5', 'k':'5', 'l':'5',
'm':'6', 'n':'6', 'o':'6',
'p':'7', 'q':'7', 'r':'7',
's':'8', 't':'8', 'u':'8', 'v':'8',
'w':'9', 'x':'9', 'y':'9', 'z':'9'
}
def insert(word):
node = start
for letter in word:
key = keyboard.get(letter)
if key == None:
continue
check = node.get(key)
if check == None:
check = node.set(key, Node())
node = check
check.add(word)
def compose(sequence):
node = start
for letter in sequence:
node = node.get(letter)
print node.wordlist
L'ho testato in maniera molto blanda, quindi potreste trovarci dei bug... cercherò anche di ripulirlo...
DanieleC88
15-07-2010, 12:08
Ma gugoXX? La lista di sequenze da testare? :D
Comunque credo che il problema maggiore per tutti sia il caricamento del dizionario e l'occupazione di memoria...
Se carico tutto, il processo di python mi va sui 160mb, tolti i 10-20mb per l'interprete stiamo a 140mb... un po' troppi.
Limitando la lunghezza delle parole prendendo max quelle lunghe 10 già si va molto meglio, con il processo di python che occupa sotto i 30mb totali :D
Ma gugoXX? La lista di sequenze da testare? :D
Arriva arriva... scusate sono proprio preso.
DanieleC88
15-07-2010, 13:28
Non c'è fretta per la lista, è che cominciavo a darti per disperso. :p
Comunque credo che il problema maggiore per tutti sia il caricamento del dizionario e l'occupazione di memoria...
Basta non caricare il dizionario e non occupare memoria ! :D
Si possono lasciare i dati su disco e andare a prendere i dati che servono in molti modi diversi, il piu' semplice e' probabilmente quello di usare un piccolo database come sqlite.
Soluzione in python+sqlite3:
Preparazione del database
import sqlite3
table = { 'a' : 2,
'b' : 2,
'c' : 2,
'd' : 3,
'e' : 3,
'f' : 3,
'g' : 4,
'h' : 4,
'i' : 4,
'j' : 5,
'k' : 5,
'l' : 5,
'm' : 6,
'n' : 6,
'o' : 6,
'p' : 7,
'q' : 7,
'r' : 7,
's' : 7,
't' : 8,
'u' : 8,
'v' : 8,
'w' : 9,
'x' : 9,
'y' : 9,
'z' : 9
}
def wordToCodes(word):
code = 0
result = []
for c in word:
code = code*10 + table.setdefault(c,0)
result.append( code )
return result
conn = sqlite3.connect('dict.sqlite')
c = conn.cursor()
c.execute('''create table dict (number integer, word text)''')
words = file('dict.txt').read().split()
for w in words:
for code in wordToCodes(w):
c.execute("insert into dict values (%d,'%s')" % (code, w))
conn.commit()
Programma vero e proprio:
import sqlite3
conn = sqlite3.connect('dict.sqlite')
c = conn.cursor()
code = raw_input()
c.execute( 'select word from dict where number=%s' % code )
for row in c:
print row[0]
Poche righe e ragionevolmente veloce
Programma vero e proprio:
import sqlite3
conn = sqlite3.connect('dict.sqlite')
c = conn.cursor()
code = raw_input()
c.execute( 'select word from dict where number=%s' % code )
for row in c:
print row[0]
Poche righe e ragionevolmente veloce
Per curiosità, quanto dura una ricerca con il database ?
Per curiosità, quanto dura una ricerca con il database ?
Sulla mia macchina circa 0.35 secondi che e' piu' o meno il tempo che ci mette il tuo codice.
tieni presente pero' che il mio programma cerca anche quelle che iniziano col codice, mettendo solo quelle di lunghezza corretta potrebbe essere piu' basso.
Ma solo la ricerca ? A me una ricerca dura circa 9 microsecondi.
La costruzione della mia struttura dati prende la maggior parte del tempo. Di fatto la parte della costruzione della struttura è equivalente all'inserimento dei dati nel database ;)
Ovviamente mantenendo costante il dizionaro potrei studiare una tecnica per il caricamento della struttura dati molto più veloce, in modo da poter eseguire le ricerche più efficientemente, per poi andare a caricare questa struttura direttamente da disco.
Si in effetti può essere una soluzione :D.
Comunque ho portato il mio programma da Python a C (che salto eh :sofico: ), il meccanismo è lo stesso, un automa, i cui stati sono fatti in questa maniera:
#define NUMBERS 10
typedef struct state
{
struct state* table[NUMBERS];
List* words;
} State;
La tabella di transizione di stato anziché essere un hashmap questa volta è un array di puntatori ad altri stati, lungo 10 bytes, uno per ogni carattere da 0 a 9.
Queste sono le funzioni chiave:
void WordAdd(char* word, State* state)
{
if (!state->words)
state->words = newList();
Node* p = newNode(word);
ListAdd(p, state->words);
}
void Insert(char* word, State* init)
{
if (!word || !init)
return;
char* c = word;
State* state = init;
do
{
int key = GetKey(*c);
if (!state->table[key])
state->table[key] = newState();
state = state->table[key];
c++;
}
while (*c != '\r');
WordAdd(word, state);
}
List* Compose(const char* sequence, State* start)
{
if (!sequence || !start)
return NULL;
char* c = (char*)sequence;
State* state = start;
do
{
int key = *c & 15;
state = state->table[key];
c++;
}
while(*c!='\0' && state != NULL);
return (state != NULL ? state->words : NULL);
}
Le strutture List e Node sono implementate in maniera basilare per funzionare, le funzioni newNode(word), newState() restituiscono un puntatore ad un nuovo Nodo (preparato o meno con la parola) o ad un nuovo Stato.
Questo il risultato (compreso il caricamento del dizionario):
[giulio@linux-laptop Programs]$ time ./t9 837482
sfrisa
verita
real 0m0.604s
user 0m0.467s
sys 0m0.121s
[giulio@linux-laptop Programs]$
Testato su un portatile Toshiba con p4 1700mhz, Fedora 13 con LXDE.
Riguardo al consumo di ram caricando anche tutto il dizionario stiamo sui 30mb. E' sempre abbastanza ma decisamente meno della versione in Python.
tieni presente pero' che il mio programma cerca anche quelle che iniziano col codice
Anche il mio può farlo a costo zero.
Ma solo la ricerca ? A me una ricerca dura circa 9 microsecondi.
Si ma della ricerca senza il caricamente te ne fai poco :D. Ora e' vero che il problema iniziale e' mal posto perche' non si capisce se bisogna velocizzare una singola ricerca o diverse in fila. Nel secondo caso ovviamente il tempo di caricamento dei dati si divide tra le ricerche e il tuo approccio ha la meglio.
Sia in un caso che nell'altro cmq si tratta di un uso diverso da quello tipico del t9, dove cominci a mostrare le parole quando hai inserito un certo numero di cifre e poi continui a filtrare.
Sì, ma il mio caricamento è lungo perché costruisco l'albero in tempo reale. Quindi in teoria rispetto al tuo corrisponde sia all'inserimento nel DB che alla ricerca.
Volendo, mettendo l'albero su disco (che è di fatto quello che fa il database), anche semplicemente suddividendoli secondo i primi tre numeri, potrei caricare solo la parte dell'albero necessaria alla ricerca, in modo da rendere il caricamento dei dati un millesimo di quello che è adesso (anzi, probabilmente meno, perché l'albero viene anche visitato ogni volta che si inserisce una nuova parola).
[giulio@linux-laptop Programs]$ time ./t9 837482
sfrisa
verita
real 0m0.604s
user 0m0.467s
sys 0m0.121s
[giulio@linux-laptop Programs]$
Ci deve essere un problemino, magari di semplice risoluzione, perché sfrisa è 737472
Sì, ma il mio caricamento è lungo perché costruisco l'albero in tempo reale. Quindi in teoria rispetto al tuo corrisponde sia all'inserimento nel DB che alla ricerca.
Vero, ma la differenza e' che nel mio caso l'utente non si accorge del caricamento perche' e' stato fatto a priori.
Volendo, mettendo l'albero su disco (che è di fatto quello che fa il database), anche semplicemente suddividendoli secondo i primi tre numeri, potrei caricare solo la parte dell'albero necessaria alla ricerca, in modo da rendere il caricamento dei dati un millesimo di quello che è adesso (anzi, probabilmente meno, perché l'albero viene anche visitato ogni volta che si inserisce una nuova parola).
Eh lo so anche io che il trucco sta nel tenere la roba sul disco, il problema e' riuscire a trovare il giusto compromesso tra semplicita' del codice, cpu, memoria e spazio su disco.
Supponendo ad esempio che la memoria permanente non sia un problema, con il seguente codice si pregenerano tutte le soluzioni
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <fstream>
using namespace std;
char charButton[128] = { '0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
'0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
'0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
'0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
'0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
'0', '0', '0', '0', '0', '0', '0', '0', '0', '0',
'0', '0', '0', '0', '0', '2', '2', '2', '3', '3',
'3', '4', '4', '4', '5', '5', '5', '6', '6', '6',
'7', '7', '7', '7', '8', '8', '8', '9', '9', '9',
'9', '0', '0', '0', '0', '0', '0', '2', '2', '2',
'3', '3', '3', '4', '4', '4', '5', '5', '5', '6',
'6', '6', '7', '7', '7', '7', '8', '8', '8', '9',
'9', '9', '9', '0', '0', '0', '0', '0' };
void computeCodes( const string& word, vector<string>& codes )
{
string code;
codes.clear();
for ( size_t i=0 ; i<word.size(); ++i )
{
code.push_back( charButton[word[i]]);
codes.push_back(code);
}
}
int main(int argc, char** argv )
{
ifstream input( argv[1] );
string word;
while (input >> word )
{
cout << word << ' '; //endl;
vector<string> codes;
computeCodes( word, codes );
for ( size_t i=0; i<codes.size(); ++i )
{
ofstream out( codes[i].c_str(), ios::app );
out << word << endl;
cout << codes[i] << ' ';
}
cout << endl;
}
}
E poi si trovano le soluzioni in tempo praticamente istantaneo con il seguente
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
int main()
{
string s;
while ( cin >> s )
{
ifstream in(s.c_str());
string t;
while ( in >> t )
{
cout << t << endl;
}
}
}
Semplice (4 MB di ram totali occupati, e si potrebbero chiaramente diminuire), veloce (pochi microsecondi sul mio netbook ) e a prova di errore :D . Basta avere l'accortezza di usare un filesystem che gestisca senza patemi mezzo milione di file in una cartella :asd:
DanieleC88
18-07-2010, 23:41
Non avendo niente di meglio da fare stasera, ho rivisto un po' la mia soluzione. Quella dell'alto giorno era una cosa da 5 minuti, con tutte le sue ovvie limitazioni (ovvero: caricamento rapidissimo e ricerca eterna).
Ora ho riscritto il codice in modo da velocizzare la ricerca, vagamente mi sembra che sia un'idea simile a quella di cionci e WarDuck:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import string
import time
import sys
cnm = {
'a': 2, 'b': 2, 'c': 2,
'd': 3, 'e': 3, 'f': 3,
'g': 4, 'h': 4, 'i': 4,
'j': 5, 'k': 5, 'l': 5,
'm': 6, 'n': 6, 'o': 6,
'p': 7, 'q': 7, 'r': 7, 's': 7,
't': 8, 'u': 8, 'v': 8,
'w': 9, 'x': 9, 'y': 9, 'z': 9
}
class Node(object):
def __init__(self, value=None, parent=None):
self._parent = parent
self._children = [None] * 9
self._value = []
if (value != None):
self._value.append(value)
def __str__(self):
return str(self._value)
def __getitem__(self, key):
return self._children[key]
def __setitem__(self, key, value):
self._children[key] = value
def add(self, value):
self._value.append(value)
def visit(self, n):
s = set([value[:n] for value in self._value])
for child in self._children:
if (child != None):
s |= child.visit(n)
return s
class Tree(object):
def __init__(self):
self._root = Node()
self._height = 0
def addNode(self, value):
code = [(cnm[x]-1) for x in value]
ptr = self._root
for c in code:
if (ptr[c] == None):
ptr[c] = Node()
ptr = ptr[c]
if (len(code) > self._height):
self._height = len(code)
ptr.add(value)
def getHeight(self):
return self._height
def search(self, code):
ptr = self._root
for c in code:
i = (ord(c) - ord('0') - 1)
ptr = ptr[i]
n = len(code)
return ptr.visit(n)
@staticmethod
def createFromFiles(baseName):
T = Tree()
for ext in string.ascii_uppercase:
f = open(baseName + '.' + ext)
for line in f:
try: T.addNode(line.strip())
except: pass
f.close()
return T
if __name__ == "__main__":
elapsed = 0.0
T = Tree.createFromFiles("ITALIANO")
f = open("input.txt")
for line in f:
try:
start = time.clock()
result = T.search(line.strip())
elapsed += (time.clock() - start)
for word in result:
print word
except:
print " [**] Invalid code:", code
f.close()
print
print "Total search time:", elapsed, "seconds."
sys.exit(0)
Considerando che al momento posso utilizzare solo un PC antidiluviano, il caricamento impiega un sacco di tempo (qualcosa come 30 secondi :eek: ), ma la ricerca è molto veloce (circa 0.20 secondi per 1000 sequenze numeriche).
Resta il fatto che stiamo proponendo soluzioni che favoriscono una ricerca quasi immediata ma che richiedono uno sproposito di memoria, come giustamente faceva notare WarDuck. Dubito che un cellulare di qualsiasi tipo possa dedicare memoria dell'ordine del centinaio di megabyte per scrivere un SMS... :stordita:
wingman87
19-07-2010, 00:09
Scusate ma io non ho capito una cosa: com'è possibile che il consumo di memoria salga così vertiginosamente?
Ho scritto una soluzione che a livello teorico dovrebbe consumare al più n*m spazio dove n è il numero di parole del dizionario ed m è la massima lunghezza della parola. Ora siccome il dizionario occupa 2,75 MB mi aspettavo un consumo di circa 50MB considerando l'overhead dovuto alle strutture interne... e invece mi ritrovo a consumare 980MB!!! Ma com'è possibile?
Ah, l'ho scritto in java, ecco il codice:
import java.util.ArrayList;
import java.util.List;
public class T9Tree {
int buttons[]={0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,7,7,7,7};
private T9Tree children[]=new T9Tree[8];
private List<String> words=new ArrayList<String>();
boolean root=false;
void addWord(String word){
if(word!=null && !word.equals(""))
words.add(word);
}
List<String> getWords(String numbers){
if((!root && words.size()==0) || numbers.length()==0) return words;
else return children[numbers.charAt(0)-'2'].getWords(numbers.substring(1));
}
protected T9Tree getChild(int index){
if(children[index]==null) children[index]=new T9Tree();
return children[index];
}
protected void build(){
build(0);
root=true;
}
private void build(int level){
for(String w:words){
try{
char c=w.charAt(level);
this.getChild(buttons[c-'a']).addWord(w);
}catch(IndexOutOfBoundsException e){}
}
for(int i=0;i<8;i++){
T9Tree t=this.getChild(i);
if(t.words.size()!=0) t.build(level+1);
}
}
}
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Loader {
private Loader(){
}
public static T9Tree loadTree() throws FileNotFoundException{
int buttons[]={0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,7,7,7,7};
T9Tree tree=new T9Tree();
for(char c='A';c<='Z';c++){
Scanner r=new Scanner(new File("dictionary/ITALIANO."+c));
T9Tree child=tree.getChild(buttons[c-'A']);
while(r.hasNext()){
child.addWord(r.next());
}
}
tree.build();
return tree;
}
}
import java.io.FileNotFoundException;
import java.util.List;
import java.util.Scanner;
public class UI {
public static void main(String args[]){
T9Tree tree=null;
try {
tree=Loader.loadTree();
} catch (FileNotFoundException e) {
System.out.println("Non è stato possibile aprire i file.\nErrore:\n"+e.getMessage());
return;
}
Scanner keyboard=new Scanner(System.in);
while(true){
System.out.println("Inserire il codice:");
String numbers=keyboard.next();
System.out.println("Parole per '"+numbers+"':");
List<String> words=tree.getWords(numbers);
for(String w:words){
System.out.println(w);
}
}
}
}
wingman87
19-07-2010, 03:00
Stavo riscrivendo il programma in C ma mi si blocca quando incontra "abat-jour". In effetti non capisco perché la versione in java non desse questo problema.
Pensavo di eliminare i caratteri non a-z per risolvere il problema.
EDIT: fatto, la versione in C occupa 200MB circa (che schifo)
T9Tree.c
#include <stdio.h>
#include <stdlib.h>
#include <String.h>
#include "T9Tree.h"
#define WORD_LENGTH 80
struct T9Node{
T9Tree children[8];
StringList words;
};
struct StringNode{
String word;
StringList next;
};
T9Tree newT9Tree(){
T9Tree ret=(T9Tree)malloc(sizeof(struct T9Node));
int i=0;
for(i=0;i<8;i++) ret->children[i]=NULL;
ret->words=NULL;
return ret;
}
T9Tree getChild(int index,T9Tree t){
if(t->children[index]==NULL) t->children[index]=newT9Tree();
return t->children[index];
}
void addWord(String word,StringList* list){
StringList ret=(StringList)malloc(sizeof(struct StringNode));
ret->word=word;
ret->next=*list;
*list=ret;
}
int isEmpty(StringList l){
return l==NULL;
}
void printList(StringList l){
while(l){
printf("%s\n",l->word);
l=l->next;
}
}
void build(T9Tree t,int level){
int indexes[]={0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,7,7,7,7};
StringList l=t->words;
while(l!=NULL){
if(strlen(l->word)>level){
char selector=l->word[level];
selector-='a';
addWord(l->word,&(getChild(indexes[selector],t)->words));
}
l=l->next;
}
int i;
for(i=0;i<8;i++){
if(!isEmpty(getChild(i,t)->words)){
build(getChild(i,t),level+1);
}
}
}
StringList getWordsInternal(String code,T9Tree t,int level){
if(level==strlen(code)) return t->words;
return getWordsInternal(code,getChild(code[level]-'2',t),level+1);
}
StringList getWords(String code,T9Tree t){
return getWordsInternal(code,t,0);
}
void delNewline(String *s){
int len=strlen(*s);
int i;
for(i=len-1;i>=0;i--){
if((*s)[i]<'a' || (*s)[i]>'z') (*s)[i]='\0';
else return;
}
}
void cleanWord(String *s){
delNewline(s);
int len=strlen(*s);
char temp[WORD_LENGTH];
strcpy(temp,*s);
int j=0;
int i;
for(i=0;i<len;i++){
if(temp[i]>='a' && temp[i]<='z'){
(*s)[j]=temp[i];
j++;
}
}
(*s)[j]='\0';
}
T9Tree loadDict(){
char c;
char path[22];
T9Tree ret=newT9Tree();
for(c='A';c<='Z';c++){
strcpy(path,"dictionary/ITALIANO."); path[20]=c; path[21]='\0';
FILE *f=fopen(path,"r");
if(f!=NULL){
while(!feof(f)){
String longword=(String)malloc(sizeof(char)*WORD_LENGTH);
if(fgets(longword,WORD_LENGTH,f)){
cleanWord(&longword);
int length=strlen(longword);
if(length>0){
String word=(String)malloc(sizeof(char)*length+1);
strcpy(word,longword);
addWord(word,&(ret->words));
}
}
free(longword);
}
fclose(f);
}else printf("Errore nell'apertura di %s\n",path);
}
build(ret,0);
return ret;
}
T9Tree.h
typedef char* String;
typedef struct T9Node* T9Tree;
typedef struct StringNode* StringList;
T9Tree loadDict();
StringList getWords(String,T9Tree);
void printList(StringList);
UI.c
#include "T9Tree.h"
int main(int argc, char** argv){
char input[20];
printf("Sto caricando il dizionario...\n");
T9Tree t=loadDict();
printf("Dizionario caricato!\n");
while(1){
printf("Inserisci il codice: ");
scanf("%s",input);
printf("Parole per '%s':\n",input);
printList(getWords(input,t));
}
}
wingman87
19-07-2010, 08:33
Piccolissima ottimizzazione (perché non ci ho pensato prima?) che fa scendere il consumo a 67MB (finalmente un valore "decente"!)
T9Tree.c
#include <stdio.h>
#include <stdlib.h>
#include <String.h>
#include "T9Tree.h"
#define WORD_LENGTH 80
struct T9Node{
T9Tree children[8];
StringList words;
};
struct StringNode{
String word;
StringList next;
};
T9Tree newT9Tree(){
T9Tree ret=(T9Tree)malloc(sizeof(struct T9Node));
int i=0;
for(i=0;i<8;i++) ret->children[i]=NULL;
ret->words=NULL;
return ret;
}
T9Tree getChild(int index,T9Tree t){
if(t->children[index]==NULL) t->children[index]=newT9Tree();
return t->children[index];
}
void addWord(String word,StringList* list){
StringList ret=(StringList)malloc(sizeof(struct StringNode));
ret->word=word;
ret->next=*list;
*list=ret;
}
int isEmpty(StringList l){
return l==NULL;
}
void printList(StringList l){
while(l){
printf("%s\n",l->word);
l=l->next;
}
}
void build(T9Tree t,int level){
int indexes[]={0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,7,7,7,7};
StringList l=t->words;
while(l!=NULL){
if(strlen(l->word)>level){
char selector=l->word[level];
selector-='a';
addWord(l->word,&(getChild(indexes[selector],t)->words));
}
l=l->next;
}
int i;
for(i=0;i<8;i++){
if(t->children[i] && !isEmpty(getChild(i,t)->words)){
build(getChild(i,t),level+1);
}
}
}
StringList getWordsInternal(String code,T9Tree t,int level){
if(level==strlen(code)) return t->words;
return getWordsInternal(code,getChild(code[level]-'2',t),level+1);
}
StringList getWords(String code,T9Tree t){
return getWordsInternal(code,t,0);
}
void delNewline(String *s){
int len=strlen(*s);
int i;
for(i=len-1;i>=0;i--){
if((*s)[i]<'a' || (*s)[i]>'z') (*s)[i]='\0';
else return;
}
}
void cleanWord(String *s){
delNewline(s);
int len=strlen(*s);
char temp[WORD_LENGTH];
strcpy(temp,*s);
int j=0;
int i;
for(i=0;i<len;i++){
if(temp[i]>='a' && temp[i]<='z'){
(*s)[j]=temp[i];
j++;
}
}
(*s)[j]='\0';
}
T9Tree loadDict(){
char c;
char path[22];
T9Tree ret=newT9Tree();
for(c='A';c<='Z';c++){
strcpy(path,"dictionary/ITALIANO."); path[20]=c; path[21]='\0';
FILE *f=fopen(path,"r");
if(f!=NULL){
while(!feof(f)){
String longword=(String)malloc(sizeof(char)*WORD_LENGTH);
if(fgets(longword,WORD_LENGTH,f)){
cleanWord(&longword);
int length=strlen(longword);
if(length>0){
String word=(String)malloc(sizeof(char)*length+1);
strcpy(word,longword);
addWord(word,&(ret->words));
}
}
free(longword);
}
fclose(f);
}else printf("Errore nell'apertura di %s\n",path);
}
build(ret,0);
return ret;
}
Ci deve essere un problemino, magari di semplice risoluzione, perché sfrisa è 737472
Si, la 's' l'ho abbinata al numero 8 :D.
7 - pqr
8 - stuv
Invece doveva essere al 7 :Prrr:
@wingman: 200mb per la versione in C, sono parecchi, la mia versione in Python ne occupava 160 col dizionario completo, considerando i 20-30mb dell'interprete...
In C dovrebbe occupare molto meno.
La mia versione comunque non da i risultati parziali (e credo che per farlo dovrebbe effettivamente consumare più memoria, almeno per come l'ho fatto io, ottima tuttavia l'osservazione di cionci sul fatto che caricando una parola hai automaticamente tutti i prefissi di essa)...
La mia idea iniziale era quella di memorizzare tutte le parole in maniera che "un carattere = un nodo", in questo modo sarebbe abbastanza semplice sia ottimizzare la questione dei prefissi (esistono cammini in comune, quindi risparmi effettivamente sul numero di nodi totali) che eventualmente trovare i nodi restanti dato un prefisso (the power of recursion :D).
Tuttavia dato che l'input è una sequenza di numeri ci si sarebbe trovati di fronte ad un automa non deterministico, dato che ad ogni numero sono associate 3-4 lettere.
L'idea quindi è stata che ogni nodo effettivamente contenesse le parole associate alla sequenza di numeri in input per arrivare a quel nodo.
Edit: uno screen del programma all'opera ->
http://img198.imageshack.us/img198/1589/97832011.th.png (http://img198.imageshack.us/i/97832011.png/)
Uploaded with ImageShack.us (http://imageshack.us)
Eh lo so anche io che il trucco sta nel tenere la roba sul disco, il problema e' riuscire a trovare il giusto compromesso tra semplicita' del codice, cpu, memoria e spazio su disco.
Se ia struttura in memoria è già contenuta, automaticamente fare il dump della struttura su disco genererà un file di dimensione contenuta.
Se ia struttura in memoria è già contenuta, automaticamente fare il dump della struttura su disco genererà un file di dimensione contenuta.
Se la struttura dati contiene puntatori un dump diretto non e' molto utile (a meno di usare una mmap su un indirizzo prefissato e un allocatore personalizzato, cosa che potrebbe anche essere carina provare a fare)
Se la struttura dati contiene puntatori un dump diretto non e' molto utile
Non ho mai detto di voler fare un dump diretto, ma un dump cambiando gli indirizzi con la posizione nel file ;)
Vincenzo1968
19-07-2010, 12:31
ruby! :)
L'ho riscritto in C usando una perfect hashing function con la lib cmph
...
Sta un po' a compilare e l'eseguibile è di 13.6 MB :D ma è VELOCE!
Source ed eseguibile qui (http://rikiji.it/data/dichash.tar.gz), serve libcmph0
Se interessa impacchetto anche il source usato per creare l'hash (CHM)
Si in effetti può essere una soluzione :D.
Comunque ho portato il mio programma da Python a C (che salto eh :sofico: ), il meccanismo è lo stesso, un automa, i cui stati sono fatti in questa maniera:
...
Testato su un portatile Toshiba con p4 1700mhz, Fedora 13 con LXDE.
Riguardo al consumo di ram caricando anche tutto il dizionario stiamo sui 30mb. E' sempre abbastanza ma decisamente meno della versione in Python.
Stavo riscrivendo il programma in C ma mi si blocca quando incontra "abat-jour". In effetti non capisco perché la versione in java non desse questo problema.
Pensavo di eliminare i caratteri non a-z per risolvere il problema.
EDIT: fatto, la versione in C occupa 200MB circa (che schifo)
...
:yeah: :winner: :yeah:
DanieleC88
19-07-2010, 12:50
Oddio chi è rispuntato dagli inferi! :eekk:
Mo lo porto pure io in C, per la tua delizia! :p
EDIT: anziché farlo a mano, l'ho fatto tradurre in C++ a Shed Skin (http://code.google.com/p/shedskin/) (gran bel progetto! :D), ed ora è circa 4 volte più veloce (8 secondi anziché 30 per caricamento e ricerca).
Sembra che sia leggermente aumentato il tempo di ricerca (intorno a 0.5 secondi invece che 0.1/0.2 secondi), ma forse è dovuto all'uso di clock().
ARI-EDIT: infatti clock() non andava bene, mi sa, per cui ho ripiegato su time() che mi dà circa 0.5 secondi per la ricerca in Python e 1.0 secondi per la ricerca in C++. :wtf:
Vincenzo1968
19-07-2010, 13:50
Oddio chi è rispuntato dagli inferi! :eekk:
Mo lo porto pure io in C, per la tua delizia! :p
...
:yeah: :yeah: :yeah: :winner: :winner: :winner: :yeah: :yeah: :yeah:
A quanto ho capito a Vincenzo piace molto il C :sofico: ... beh in effetti smanettare con i puntatori a volte non ha prezzo.
I puntatori a funzioni poi permettono di fare cose carine :D.
Del tipo
void ForNodeIn(List* ls, (void)(*func)(Node* p))
{
if (!func || !ls || !ls->beg)
return;
Node* it = ls->beg;
while (it)
{
func(it);
it = it->next;
}
}
void Do(Node* p)
{
printf("0%x, ", p);
}
int main(void)
{
List* ls = newList();
ForNodeIn(ls, Do);
return 0;
}
La sfida col C è riuscire ad essere eleganti nonostante il linguaggio :D.
DanieleC88
19-07-2010, 15:25
Memory leak!!! :eekk:
:p
Memory leak!!! :eekk:
:p
Dove? Nel main?
In teoria quando chiudi un processo tutte le aree di memoria associate ad esso dovrebbero essere rilasciate, quindi non credo ci sia effettivamente un memory leak.
Libero di sbagliarmi naturalmente, ma un memory leak dovrebbe essere tale a processo attivo.
DanieleC88
19-07-2010, 16:26
Tanto per chiarire: lo dicevo in tono scherzoso! (Non è che riattacchiamo un flame pure qua... :mbe: )
Comunque sì, è una cosa che di solito il sistema operativo fa, ma è solo una cosa praticamente vera, non teoricamente vera (non è compito del sistema operativo di rimediare agli errori di programmazione). La deallocazione delle risorse (di ogni tipo, mica solo memoria) è sempre da farsi.
ciao ;)
Tanto per chiarire: lo dicevo in tono scherzoso! (Non è che riattacchiamo un flame pure qua... :mbe: )
Comunque sì, è una cosa che di solito il sistema operativo fa, ma è solo una cosa praticamente vera, non teoricamente vera (non è compito del sistema operativo di rimediare agli errori di programmazione). La deallocazione delle risorse (di ogni tipo, mica solo memoria) è sempre da farsi.
ciao ;)
No beh hai fatto bene a dirlo perché solo così uno può imparare dai propri errori :D, comunque in effetti ho provato con valgrind e il problema si pone.
In genere sono attento a deallocare dove possibile, tuttavia in questo caso (che poi era un esempio scritto al volo) non credevo fosse necessario.
Buono a sapersi comunque.
wingman87
19-07-2010, 18:39
@wingman: 200mb per la versione in C, sono parecchi, la mia versione in Python ne occupava 160 col dizionario completo, considerando i 20-30mb dell'interprete...
Sì è vero ma se vedi il post successivo non avevo fatto un'ottimizzazione alquanto banale e il consumo è sceso a 67MB.
La mia idea è semplicissima, ho un albero in cui ogni nodo contiene una lista di parole e 8 puntatori a sottoalberi che contengono una suddivisione della lista contenuta nel nodo stesso.
Ho quindi nella radice tutte le parole del dizionario, poi nel primo sottoalbero avrò tutte le parole che iniziano con a,b,c, nel secondo quelle che iniziano con d,e,f e così via. Nei sottoalberi reitero la suddivisione basata però sulle lettere successive. La ricerca in questo modo è praticamente istantanea. E il caricamento sul mio pc impiega circa 0.75 secondi.
Se non avessi considerato i check parziali il consumo credo che sarebbe diminuito parecchio.
Avevo anche pensato di fare un'altra ottimizzazione: quando la lista di parole è più corta di 100 elementi (o anche di più, bisognerebbe fare qualche test) si potrebbe smettere di suddividere e al momento in cui dovremo cercare un codice in tali liste fare una semplice ricerca sequenziale.
Niente ho finito quel lavoro con la licenza apple e sono venuto a dire la mia :D
La mia soluzione ad albero:
-occupa 6 mb in memoria
-costruisce il database in 0.3 secondi
-ricerca sempre sotto i 30 microsecondi
-trova le stringhe incomplete
E al momento uso std vector e std string per i risultati :D
Per la sequenza di esempio il risultato è:
agam
bian
bico
cham
chan
ciam
cian
ciao
cibo
cico
Ah è anche lunga manco 100 righe.
Ryuzaki_Eru
19-07-2010, 18:57
Dove è il codice? :D
Senza codice sei solo chiacchere e distintivo :D.
DanieleC88
19-07-2010, 19:01
Dove è il codice? :D
È codice proprietario. :O
Ryuzaki_Eru
19-07-2010, 19:04
È codice proprietario. :O
Addirittura :eek: :O
DanieleC88
19-07-2010, 19:12
La mia soluzione ad albero:
-occupa 6 mb in memoria
Con questa sono particolarmente interessato al codice, visto che:
[jmc@gorgoroth contest]$ du -shc ITALIANO.[A-Z]
172K ITALIANO.A
60K ITALIANO.B
172K ITALIANO.C
104K ITALIANO.D
80K ITALIANO.E
88K ITALIANO.F
84K ITALIANO.G
4,0K ITALIANO.H
304K ITALIANO.I
4,0K ITALIANO.J
4,0K ITALIANO.K
76K ITALIANO.L
168K ITALIANO.M
48K ITALIANO.N
80K ITALIANO.O
272K ITALIANO.P
12K ITALIANO.Q
332K ITALIANO.R
572K ITALIANO.S
192K ITALIANO.T
20K ITALIANO.U
68K ITALIANO.V
4,0K ITALIANO.W
4,0K ITALIANO.X
4,0K ITALIANO.Y
8,0K ITALIANO.Z
2,9M totale
il solo dizionario occupa quasi 3 megabyte! :mbe:
No niente ho fatto male il conto, in realtà occupa n_parole * 27 * sizeof( void* ) che in realtà è una cifra :D
Al momento sarebbero 108 mb :sofico:
Il codice prima o poi lo posto, però ho abbassato il caricamento a 0.11 secondi.
DanieleC88
19-07-2010, 19:25
No niente ho fatto male il conto, in realtà occupa n_parole * 27 * sizeof( void* ) che in realtà è una cifra :D
Al momento sarebbero 108 mb :sofico:
Ah mbe! :sofico:
No perché se avevi fatto una cosa del genere eri un dio dell'informatica. :Prrr:
Quelle erano le stime/speranze in fase di progettazione :O
Simock85
19-07-2010, 22:00
Potrei utilizzare un database sqlite?
cdimauro
19-07-2010, 22:37
No beh hai fatto bene a dirlo perché solo così uno può imparare dai propri errori :D, comunque in effetti ho provato con valgrind e il problema si pone.
In genere sono attento a deallocare dove possibile, tuttavia in questo caso (che poi era un esempio scritto al volo) non credevo fosse necessario.
Buono a sapersi comunque.
Considera che non tutti i s.o. hanno il tracking delle risorse allocate.
Ad esempio, se per AmigaOS rilasciassi un programma del genere, ti troveresti in battibaleno i fanatici all'uscio e con le mazze ferrate ad aspettarti. :D
Simock85
20-07-2010, 01:19
Ecco il mio accrocco, ho calcolato in precedenza l'hash word -> value e ho salvato i records in un csv, aggiornabile col metodo Aggiorna della classe dizionario. All'avvio leggo il csv (con la libreria csv che è scritta in c quindi dovrebbe far risparmiare tempo rispetto a uno split ',') e lo carico in un array; scorrere il csv a ogni ricerca è da pazzi, interprete + array sono 27MB in memoria.
#!/usr/bin/env python
#===============================================================================
# Created on 19/lug/2010
#
# author: Simock85
#===============================================================================
import csv
class T9():
def __init__ (self):
self.convTab = {'2' : ['a', 'b', 'c'],
'3' : ['d', 'e', 'f'],
'4' : ['g', 'h', 'i'],
'5' : ['j', 'k', 'l'],
'6' : ['m', 'n', 'o'],
'7' : ['p', 'q', 'r', 's'],
'8' : ['t', 'u', 'v'],
'9' : ['w', 'x', 'y', 'z']}
def firstLetter(self, num):
return self.convTab[num]
def strConv(self, word):
num = []
for letter in word:
for i, j in self.convTab.iteritems():
if letter in j:
num.append(i)
return ''.join(num)
class Dizionario():
def Aggiorna(self):
t9 = T9()
lets = 'abcdefghijklmnopqrstuvwxyz'
f_wls = open ('wordlist.txt', 'wb')
wls = csv.writer (f_wls)
for let in lets:
file = 'ITALIANO.%s' % (let.upper())
f = open (file, 'r')
for word in f.readlines():
word = word.strip('\n')
value = t9.strConv(word)
wls.writerow([word, value])
f.close()
f_wls.close()
def Trova(self, num, db):
lungh = len(num)
words = []
for i, j in db.iteritems():
if num == j[:lungh] and i[:lungh] not in words:
words.append(i[:lungh])
return words
def Leggi(self):
db = {}
f = open ('wordlist.txt', 'rb')
linee = csv.reader(f)
for word, value in linee:
db[word] = value
return db
if __name__ == '__main__':
app = Dizionario()
#app.Aggiorna()
db = app.Leggi()
num = raw_input('T9: ')
words = app.Trova(num, db)
words.sort()
string = '\n'.join(words)
f = open ('words.txt', 'w')
f.write(string)
f.close()
Credo che l'utilizzo di un DBMS sia la soluzione migliore, non si carica nulla in memoria e le query sono piuttosto veloci.
Ah mbe! :sofico:
No perché se avevi fatto una cosa del genere eri un dio dell'informatica. :Prrr:
Spe.
Ho corretto un bug, ho compilato a 32 bit e ora occupa solamente 39 mb :D
In più il numero medio di figli nei nodi non foglia è 1.67, mentre io gli alloco 26 puntatori a cranio.
E' possibilissimo usare una lista ordinata senza perdere in prestazioni e avvicinando il consumo di memoria minimo.
In più adesso mi salvo anche il parent ma non credo che serva davvero.
Per cui magari 6 mb no, ma 10 mi sembrano ragionevoli :sofico:
PS: misteriosamente ora che ho riacceso il pc la ricerca non scende sotto i 50 ms. Mistero della fede.
PS: misteriosamente ora che ho riacceso il pc la ricerca non scende sotto i 50 ms. Mistero della fede.
Solo la ricerca o incluso anche il caricamento ?
Simock85
20-07-2010, 13:26
Ho provato con sqlite, al primo avvio crea il database (il tempo impiegato è notevole, 50" su un Atom). Una query impiega 0,70".
#!/usr/bin/env python
#===============================================================================
# Created on 19/lug/2010
#
# author: Simock85
#===============================================================================
import sqlite3
import os.path
import sys
#import cProfile
class T9():
def __init__ (self):
self.convTab = {'a' : '2', 'b' : '2', 'c' : '2',
'd' : '3', 'e' : '3', 'f' : '3',
'g' : '4', 'h' : '4', 'i' : '4',
'j' : '5', 'k' : '5', 'l' : '5',
'm' : '6', 'n' : '6', 'o' : '6',
'p' : '7', 'q' : '7', 'r' : '7', 's' : '7',
't' : '8', 'u' : '8', 'v' : '8',
'w' : '9', 'x' : '9', 'y' : '9', 'z' : '9'}
def strConv(self, word):
num = []
for letter in word:
if self.convTab.has_key(letter):
n = self.convTab[letter]
num.append(n)
else: num.append('1')
return ''.join(num)
class Database():
def Crea(self):
conn = sqlite3.connect('wordlist.db')
c = conn.cursor()
c.execute('''create table dict (word text, value text)''')
conn.commit()
c.close()
def Add(self, db):
conn = sqlite3.connect('wordlist.db')
c = conn.cursor()
for word, value in db.iteritems():
c.execute('insert into dict values (?, ?)',
(word, value))
conn.commit()
c.close()
def Query(self, value):
value = value + '%'
conn = sqlite3.connect('wordlist.db')
c = conn.cursor()
c.execute('select word from dict where value like ? order by word',
(value, ))
w_list = []
for res in c.fetchall():
w_list.append(res[0])
return w_list
class Dizionario():
def __init__ (self):
self.db = Database()
def Aggiorna(self):
self.db.Crea()
t9 = T9()
lets = 'abcdefghijklmnopqrstuvwxyz'
dict = {}
for let in lets:
file = 'ITALIANO.%s' % (let.upper())
f = open (file, 'r')
for word in f.readlines():
word = word.strip('\n')
value = t9.strConv(word)
dict[word] = value
f.close()
self.db.Add(dict)
def Trova(self, num):
lungh = len(num)
db = self.db.Query(num)
words = []
for word in db:
if word[:lungh] not in words:
words.append(word[:lungh])
return words
def DbCheck(self):
check = os.path.exists('wordlist.db')
return check
if __name__ == '__main__':
app = Dizionario()
def main():
num = raw_input('T9: ')
if num == 'x':
sys.exit(0)
else:
words = app.Trova(num)
for word in words:
print word
main()
if app.DbCheck():
#cProfile.run('main()', 'main.txt')
main()
else:
#cProfile.run('app.Aggiorna()', 'dbprof.txt')
app.Aggiorna()
main()
Adesso do un'occhiata al risultato del profile, vediamo dove devo ottimizzare
Solo la ricerca o incluso anche il caricamento ?
Solo la ricerca, infatti è tanto.
Per qualche motivo oggi è cresciuto ulteriormente a 100 ms, ma il bello è che non sto toccando il codice relativo alla ricerca :D
Su Mac c'è un modo accurato di vedere il consumo di RAM che non sia l'Activity Manager?
A me la sola ricerca ci mette circa 10 micro secondi...
Beh sembra che ci siano delle instabilità nel SO cmq... se la faccio girare 10000 volte ci mette 21 ms di media, e già è meglio.
Poi il 60% del tempo è dovuto all'up-recursion dalle foglie che ha trovato ai loro parent per ricomporre le parole.
Però credo che si possa fare direttamente "a scendere" con una struttura dati adatta.
banryu79
20-07-2010, 14:24
Beh sembra che ci siano delle instabilità nel SO cmq... se la faccio girare 10000 volte ci mette 21 ms di media, e già è meglio.
Bho, magari dopo una riaccensione, se fai girare un tot. di volte lo stesso eseguibile ne ottimizza meglio la paginazione e hai accessi più rapidi in memoria?
Sennò chiamiamo Martin Mystere :D
In release fa una media di 10 ms, bene :D
Cmq non saprei, sono su Mac e lo conosco poco... su Win non è mai capitata una cosa del genere in C++, massimo oscillazioni di pochi secondi.
Per essere sicuro ora gli mando sequenze random di 4 caratteri.
EDIT: su 10000 sequenze random di 4 caratteri il tempo medio migliora a 3.6 ms :D
E' perchè molte non hanno senso, e quindi non chiama mai la funzione che ricostruisce la stringa. Mi devo dar da fare a cassarla :asd:
Vincenzo1968
20-07-2010, 15:06
Ma gugoXX? La lista di sequenze da testare? :D
*
Risposta del 15/07/2010:
Arriva arriva... scusate sono proprio preso.
Cionci: Puoi modificare il titolo del thread aggiungendo la numerazione? Questo è il n° 18. Gli altri, lo ricordo per i nuovi utenti, sono questi:
Contest 1: Bitmap (http://www.hwupgrade.it/forum/showthread.php?t=1784948)
Contest 2: Ricerca (http://www.hwupgrade.it/forum/showthread.php?t=1785752)
Contest 3: La somma (http://www.hwupgrade.it/forum/showthread.php?t=1787500)
Contest 4: DNA (http://www.hwupgrade.it/forum/showthread.php?t=1791293)
Contest 5: Sottomatrici (http://www.hwupgrade.it/forum/showthread.php?t=1799059)
Contest 6: Parsing (http://www.hwupgrade.it/forum/showthread.php?t=1850150)
Contest 7: Il lotto (http://www.hwupgrade.it/forum/showthread.php?t=1839674)
Proposta (http://www.hwupgrade.it/forum/showthread.php?t=1872715)
Contest 8: Compattamento Barionico (http://www.hwupgrade.it/forum/showthread.php?t=1877648)
Contest 9: Divisori dei numeri triangolari (http://www.hwupgrade.it/forum/showthread.php?t=1882576)
Contest 10: Numeri palindormi (Semplice) (http://www.hwupgrade.it/forum/showthread.php?t=1883750)
Contest 11: Change. NP-Hard. (http://www.hwupgrade.it/forum/showthread.php?t=1884158)
Contest 12: Il muro (http://www.hwupgrade.it/forum/showthread.php?t=1890800)
Contest 13: Date (http://www.hwupgrade.it/forum/showthread.php?t=1981159)
Contest 14: Corsa delle macchine (http://www.hwupgrade.it/forum/showthread.php?t=1982858)
Contest 15: sudoku (http://www.hwupgrade.it/forum/showthread.php?t=1995326)
Contest 16: Intervalli (http://www.hwupgrade.it/forum/showthread.php?t=2006573)
Contest 17: Compilatori e interpreti. Parte I: interpreti. (http://www.hwupgrade.it/forum/showthread.php?t=2030843)
Simock85
20-07-2010, 15:13
Io continuo per la strada del database piuttosto che caricare in memoria, ho ottimizzato la conversione word -> digits utilizzando la funzione built-in string.maketrans che crea una matrice di traduzione tra 2 stringhe. Il tempo di generazione del database è passato a 25" contro i 53" di prima. Il grosso del tempo se lo portano via la creazione del database, della tabella e tutti gli execute (19 secondi), il resto è l'apertura dei file del dizionario, conversione in digits, strip del carattere fine linea.
class T9():
def __init__ (self):
self.chars = string.lowercase
self.digits = '22233344455566677778889999'
self.charToDigits = string.maketrans(self.chars, self.digits)
def strConv(self, word):
num = word.translate(self.charToDigits)
return num
Nussun altro sta provando con un file locale piuttosto che array in memoria?
Bene, posso dire che matematicamente il mio programma occupa 22.56 mb.
n_nodi * ( 1 + sizeof( void* ) ) + n_nodi_interni * 26 * sizeof( void* )
Cioè ogni nodo ha un carattere e un puntatore + un overhead sul dizionario liscio pari a n_nodi_interni * 26 * sizeof( void* ).
Il problema è chiaramente quel "26", che è necessario per avere un accesso O(1) alla memoria... ma forse si fa anche senza.
Ora ho tolto anche il link al parent e la ricerca impiega una media di 12 ms; sembrerebbe peggiorato, ma ora il caso peggiore di 100+ ms è sparito, a fronte di un peggioramento delle stringhe dove non trova nulla. Il che mi sembra migliore.
EDIT: con la ricerca in O(n) i tempi sono impercettibilmente peggiorati ma il consumo di memoria reale è sceso a 16 mb... quello effettivo dopo il parse è 12.66 mb. Non credo si possa fare molto di meglio :D
Tra po posto il codice.
EDIT2: Se compilo con LLVM fa 7 ms. Paura e delirio.
EDIT3: mi sono stufato, quindi ciapa il codice, ora fa
-occupa 12.66 mb
-carica in 0.2 s
-ricerca in 10 ms
#include "AlphaNode.h"
#include <fstream>
namespace T9 {
class T9System
{
public:
T9System()
{
root = new AlphaNode( 0 );
}
~T9System()
{
delete root;
}
inline void addWord( const char* ptr, int len )
{
root->subTreeFromWord( ptr, ptr + len );
}
inline void parseFile( const std::string& filename )
{
using namespace std;
ifstream file( filename.c_str(), ios_base::in | ios_base::ate );
int sz = file.tellg();
char* buf = (char*)malloc( sz );
char* mem = buf; //remember to free
memset( buf, 0, sz );
file.seekg(0);
file.read( buf, sz );
file.close();
char* end = buf + sz;
char* wordStart = buf;
while( buf < end )
{
if( *buf == '\r' || *buf == '\n' )
{
if( wordStart != buf )
addWord( wordStart, buf - wordStart );
wordStart = buf + 1;
}
++buf;
}
free( mem );
}
inline void getWordsForSequence( const std::string& seq, std::vector<std::string>& words )
{
root->getWordsFromSequence( seq, words );
}
protected:
AlphaNode* root;
};
}
#include <string>
#include <vector>
#include <iostream>
#include <fstream>
namespace T9
{
class AlphaNode
{
public:
typedef unsigned char byte;
static const char association[];
static const int alphabetLenght = 'z' - 'a';
AlphaNode( char l ) :
letter( l ),
childs( NULL ),
childNumber( 0 )
{
}
~AlphaNode()
{
if( childs )
{
for( byte i = 0; childs && i < childNumber; ++i )
delete childs[i];
free( childs );
}
}
inline bool isLeaf() { return childs == NULL; }
inline AlphaNode* getNode( char c )
{
for( byte i = 0; i < childNumber; ++i )
{
if( childs[i]->letter == c )
return childs[i];
}
return NULL;
}
inline void subTreeFromWord( const char* buf, const char* end )
{
char c = *buf;
AlphaNode* node = getNode( c );
//create a new node
if( !node )
{
//lazy initialise childs
++childNumber;
if( childNumber == 1 )
childs = (AlphaNode**)malloc( sizeof( void* ) );
//extend current memory
else
childs = (AlphaNode**)realloc( childs, sizeof( void* ) * childNumber );
//create node
node = new AlphaNode( c );
childs[ childNumber - 1 ] = node;
}
//keep propagating
if( buf+1 < end )
node->subTreeFromWord( buf + 1, end );//recursion
}
//gets all the sub words at least long "len"
void getWordsFromSequence( const std::string& seq, std::vector<std::string>& res )
{
char* buf = (char*)seq.c_str();
_getWordsFromSubTree( "", buf, res );
}
protected:
char letter;
byte childNumber;
AlphaNode** childs;
void _getWordsFromSubTree( std::string prev, char* buf, std::vector<std::string>& res )
{
prev += letter; //add the current char
//last character?
if( *buf == '\0' )
{
res.push_back( prev );
return;
}
//proceed down in the tree
else if( childs )
{
int a_idx;
AlphaNode* child;
for( byte i = 0; i < childNumber; ++i )
{
child = childs[i];
//check if we are interested in this path using associations
a_idx = (*buf - '2') * 2;
if( child->letter >= association[ a_idx ] &&
child->letter <= association[ a_idx+1 ] )
child->_getWordsFromSubTree( prev, buf+1, res );
}
}
}
};
}
Si potrebbe fare di meglio, tipo evitando di fare duemila copie di std::string, evitando reallocs per ogni nuovo nodo e rendendo multithreaded la costruzione dell'albero... ma non mi vappiù :D
EDIT4 (:asd: ) con la costruzione multithread dell'albero fa 0.1 secondi o meno durante il caricamento.
Ok l'idea che mi è venuta forse è abbastanza banale e probabilmente equivale a barare :sofico: .
Ho modificato il programma che avevo fatto e sostanzialmente l'idea è quella di far caricare on-the-fly le parole relative al primo numero della sequenza.
Ad esempio se abbiamo 2426 sappiamo che tutte le parole sicuramente iniziano per A, B e C, e dunque è inutile caricare gli altri files.
Facendo così ottengo questo:
[giulio@linux-laptop Programs]$ time ./t9 2426
ciao
cibo
real 0m0.122s
user 0m0.091s
sys 0m0.022s
[giulio@linux-laptop Programs]$
Compreso caricamento e scaricamento (alla fine il programma pulisce tutte le strutture).
La memoria occupata (in questo caso di esempio) si attesta sui 4.7mb.
Ricordo che il test è fatto su un portatile Toshiba p4 1700mhz con Fedora 13 LXDE, 32bit.
Ora, delle considerazioni:
1) è chiaro che effettuare una ricerca su elementi non caricati richiede più tempo
2) il tempo medio tra un esecuzione e l'altra del programma è comunque inferiore se consideriamo che ogni istanza può fare caso a se
3) se usassimo un approccio in cui si carica il dizionario solo alla bisogna si potrebbe costruire un'insieme di parole più utilizzate e dunque ottimizzare quello
4) è un approccio probabilmente inutilizzabile in pratica
Che ne dite?
Cercherò di spremere le meningi per ottimizzare il caricamento da disco.
Andando a scrivere la mia struttura dati sul disco, rendendo quindi statica l'indicizzazione (55,4 MB di spazio su disco utilizzato), il tempo di una ricerca di 10 caratteri è circa pari al tempo di seek * il numero di lettere ;) Circa 50 microsecondi per 10 lettere.
Ovviamente occupazione di ram praticamente nulla.
Ecco il codice:
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <cstring>
using namespace std;
int toNumber(char c)
{
static int map[] = {0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,7,7,7,7};
c = tolower(c);
if(c >= 'a' && c <= 'z')
return map[(int)(c - 'a')];
return -1;
}
char toNumberChar(char c)
{
return '2' + toNumber(c);
}
class Node
{
Node ** children;
list<streampos> mList;
public:
Node():children(NULL)
{
}
bool hasChildren()
{
return children != 0;
}
bool hasChild(const int index) const
{
if(!children)
return false;
if(!children[index])
return false;
return true;
}
Node * getChild(const int index)
{
return children[index];
}
void updateMatching(const streampos file_pos)
{
mList.push_back(file_pos);
}
Node * updateNode(const int index, const streampos file_pos, const bool skip_matching)
{
if(!children)
{
children = new Node * [8];
memset(children, 0, 8 * sizeof(Node *));
}
if(!children[index])
{
children[index] = new Node();
}
if(!skip_matching)
updateMatching(file_pos);
return children[index];
}
list<streampos> & getMatchings()
{
return mList;
}
~Node()
{
if(children)
delete[] children;
}
};
class T9Tree
{
Node * root;
const string dictionary;
string prev_word;
void addWord(const string word, const unsigned int unique, const streampos file_pos)
{
Node * node = root;
bool flag = true;
for(unsigned int i = 0; i < unique; ++i)
{
int number = toNumber(word.at(i));
if(number >= 0)
node = node->updateNode(number, file_pos, flag);
flag = flag && prev_word.size() > i && prev_word.at(i) == word.at(i);
}
if(!flag)
node->updateMatching(file_pos);
prev_word = word;
}
int compareTwo(string & ref, string & word)
{
unsigned int pos = 0;
while(ref.size() > pos && word.size() > pos && ref.at(pos) == word.at(pos))
{
++pos;
}
return pos;
}
int compareThree(string & ref1, string & word, string & ref2)
{
unsigned int pos = 0;
bool flag = true, flag1 = true, flag2 = true;
while(flag)
{
flag1 = flag1 && pos < ref1.size() && ref1.at(pos) == word.at(pos);
flag2 = flag2 && pos < ref2.size() && ref2.at(pos) == word.at(pos);
++pos;
flag = (flag1 || flag2) && word.size() > pos;
}
return pos;
}
public:
T9Tree(const string fileName): dictionary(fileName), prev_word("")
{
root = new Node();
}
bool parseDictionary()
{
ifstream f(dictionary.c_str());
if(!f.is_open())
return false;
string previous;
string word;
string next;
//add first word
getline(f, previous);
streampos curr_file_pos = f.tellg();
getline(f, word);
streampos next_file_pos;
int unique = compareTwo(word, previous);
addWord(previous, unique, 0);
int word_index = 0;
while(1)
{
word_index++;
next_file_pos = f.tellg();
getline(f, next);
if(f.eof())
break;
if(next.size())
{
unique = compareThree(previous, word, next);
addWord(word, unique, curr_file_pos);
previous = word;
word = next;
curr_file_pos = next_file_pos;
}
}
//add last word
unique = compareTwo(previous, word);
addWord(word, unique, curr_file_pos);
f.close();
return true;
}
bool find(const string numbers, vector<string> &result)
{
Node * node = root;
bool mustVerify = false;
int verifyIndex = 0;
for(unsigned int i = 0; i < numbers.size(); ++i)
{
int index = numbers.at(i) - '2';
if(node->hasChild(index))
node = node->getChild(index);
else
{
if(node->hasChildren())
return false;
else
{
mustVerify = true;
verifyIndex = i;
break;
}
}
}
ifstream f(dictionary.c_str());
if(!f.is_open())
return false;
list<streampos> &l = node->getMatchings();
for(list<streampos>::iterator it = l.begin(); it != l.end(); it++)
{
streampos &pos = *it;
//cout << "Offset: " << pos << endl;
f.seekg(pos, ios_base::beg);
string s;
getline(f, s);
bool verified = true;
if(mustVerify && s.size() >= numbers.size())
{
for(unsigned int i = verifyIndex; i < numbers.size(); ++i)
{
if(toNumberChar(s.at(i)) != numbers.at(i))
{
verified = false;
break;
}
}
}
if(verified)
result.push_back(s.substr(0, numbers.size()));
}
f.close();
return result.size() > 0;
}
#define EMPTY_POS (static_cast<streampos>(-1))
void dumpNode(Node * n, ofstream & index, fstream & offset)
{
list<streampos> & m = n->getMatchings();
//init with matching file position and size
struct nodeData
{
streampos offsetPos;
unsigned int count;
} nData = {offset.tellp(), m.size()};
//write matching data to offset file
index.write((char *)&nData, sizeof(nodeData));
list<streampos>::iterator it;
for(it = m.begin(); it != m.end(); it++)
{
streampos pos = *it;
offset.write((char *)&pos, sizeof(pos));
}
streampos cDataOffset = index.tellp();
streampos cData[8];
//write placeholder for children offsets
index.write((char *)cData, sizeof(cData));
for(int i = 0; i < 8; i++)
{
cData[i] = EMPTY_POS;
if(n->hasChild(i))
{
cData[i] = index.tellp();
dumpNode(n->getChild(i), index, offset);
}
}
//write real children offsets
index.seekp(cDataOffset, ios::beg);
index.write((char *)cData, sizeof(cData));
//move to end of file
index.seekp(0, ios::end);
}
void writeToFile(string filename)
{
ofstream indexFile(filename.c_str(), ofstream::binary | ofstream::trunc);
fstream offsetFile(filename.append(".tmp").c_str(), fstream::in | fstream::out | fstream::binary | fstream::trunc);
//write placeholder for data displacement
streampos dataOffset = indexFile.tellp();
indexFile.write((char *)&dataOffset, sizeof(dataOffset));
//write tree to file
dumpNode(root, indexFile, offsetFile);
//take real data displacement
dataOffset = indexFile.tellp();
offsetFile.seekg(0, ios::beg);
//copy data from offset file at the end of the index file
while(1)
{
char buffer[4096];
offsetFile.read(buffer, sizeof(buffer));
if(offsetFile.eof())
break;
indexFile.write(buffer, offsetFile.gcount());
}
offsetFile.close();
//remove offset temporary file
remove(filename.c_str());
//write real data displacement at the beginning of the file
indexFile.seekp(0, ios::beg);
indexFile.write((char *)&dataOffset, sizeof(dataOffset));
indexFile.close();
}
bool dumpedFind(const string filename, const string numbers, vector<string> &result)
{
struct DumpedNode
{
streampos offsetPos;
unsigned int count;
streampos children[8];
} node;
streampos dataOffset;
ifstream idx(filename.c_str());
idx.read((char *)&dataOffset, sizeof(streampos));
int verifyIndex = -1;
for(unsigned int i = 0; i < numbers.size(); ++i)
{
int index = numbers.at(i) - '2';
idx.read((char *)&node, sizeof(node));
if(node.children[index] != EMPTY_POS)
idx.seekg(node.children[index], ios::beg);
else
{
verifyIndex = i;
}
}
if(verifyIndex == -1)
idx.read((char *)&node, sizeof(node));
ifstream f(dictionary.c_str());
if(!f.is_open())
return false;
idx.seekg(node.offsetPos + dataOffset, ios::beg);
for(unsigned int i = 0; i < node.count; i++)
{
streampos pos;
idx.read((char *)&pos, sizeof(pos));
//cout << "Offset: " << pos << endl;
f.seekg(pos, ios_base::beg);
string s;
getline(f, s);
bool verified = true;
if(verifyIndex >= 0)
{
if(s.size() >= numbers.size())
{
for(unsigned int i = verifyIndex; i < numbers.size(); ++i)
{
if(toNumberChar(s.at(i)) != numbers.at(i))
{
verified = false;
break;
}
}
}
else
{
verified = false;
}
}
if(verified)
result.push_back(s.substr(0, numbers.size()));
}
f.close();
idx.close();
return result.size() > 0;
}
~T9Tree()
{
delete root;
}
};
void find(T9Tree &t9, const string numbers, bool dumped = false)
{
cout << "Find " << numbers << ":" << endl;
vector<string> v;
bool result = (dumped) ? t9.dumpedFind("data.dat", numbers, v) : t9.find(numbers, v);
if(!result)
{
cout << "Corrispondenza non trovata" << endl;
}
else
{
for(vector<string>::iterator it = v.begin(); it != v.end(); it++)
{
cout << *it << endl;
}
}
}
int main(int argc, char *argv[])
{
T9Tree t9("italiano.txt");
if(argc != 2)
{
t9.parseDictionary();
t9.writeToFile("data.dat");
}
else
{
find(t9, argv[1], true);
}
return 0;
}
E questo è il file per il dizionario: http://www.mediafire.com/download.php?5unlytjj3ni
Mi serve avere un file unico per scrivere solo l'offset all'interno del file del dizionario come punto di riferimento per l'indicizzazione.
Per far costruire la struttura dati su disco basta lanciare l'eseguibile senza parametri. Se si passa un parametro allora fa la ricerca.
Vincenzo1968
21-07-2010, 14:36
Cionci, compilando il tuo codice con visual studio 2008, ho il seguente errore:
main.cpp(156) : error C3861: 'getline': identifier not found
:confused:
banryu79
21-07-2010, 14:40
Cionci, compilando il tuo codice con visual studio 2008...
E' tornato!
Vincenzo1928 is back! :eek:
Ciaoooo! :D
@EDIT:
:asd:
Vincenzo1968
21-07-2010, 14:47
E' tornato!
Vincenzo1928 is back! :eek:
Ciaoooo! :D
Da quando hanno chiuso SPA passo un po' più di tempo da queste parti.
Ciao Banryu29 :D
DanieleC88
21-07-2010, 14:47
Vincenzo1928 is back! :eek:
Ed è pure invecchiato di una quarantina d'anni! :Prrr:
E' tornato!
Vincenzo1928 is back! :eek:
Va beh che usa sempre C, ma non credo sia cosi vecchio...
Vincenzo1968
23-07-2010, 13:21
Cionci, compilando il tuo codice con visual studio 2008, ho il seguente errore:
main.cpp(156) : error C3861: 'getline': identifier not found
:confused:
Risolto. Basta includere <string>:
#include <string>
http://www.cplusplus.com/reference/string/getline/
;)
Vincenzo1968
23-07-2010, 13:40
Cionci, ottengo strani risultati:
http://img6.imageshack.us/img6/3497/contest18cionci.jpg
:confused:
In effetti c'è qualche bug, devo debuggarlo un po', ci penso la prossima settimana...
Vincenzo1968
23-07-2010, 14:15
In effetti c'è qualche bug, devo debuggarlo un po', ci penso la prossima settimana...
Minnale!!! La prossima settimana...
Volevo postare la classifica oggi. :mad:
Vabbuò, aspettiamo.
Falso allarme, avevo compilato la versione sbagliata. A me funziona. Non so quale sia il problema su VC++, vedo se riesco a darci uno sguardo.
$ time ./T9 2426
Find 2426:
agam
bian
bico
cham
chan
ciam
cian
ciao
cibo
cico
real 0m0.002s
user 0m0.000s
sys 0m0.000s
Ho dato uno sguardo su VC++, ma non riesco a risolvere in tempi brevi. La struttura di ricerca funziona perfettamente. Sono i valori degli offset che non corrispondo a quelli del file del dizionario :mbe: :confused:
vBulletin® v3.6.4, Copyright ©2000-2026, Jelsoft Enterprises Ltd.