STL containers ou Sqlite :memory:

[Andre Duarte]

Caros amigos da lista,

Estou implementando um sistema que usa um banco de dados(Sqlite) como
base de conhecimento, ou seja, ele só faz consultas à base e nunca
escreve nela.

Como um dos requisitos do sistema é DESEMPENHO, necessito carregar
estas tabelas em memória para agilizar as consultas, para isso tenho
dois cenários:

1- Carregar as tabelas em alguma* estrutura de dados, neste caso não
sei qual contêiner seria melhor já que vou fazer somente
consultas(read-only). vector<T>?? Sets<T>??

2 - Fazer um dump das tabelas do disco para a memória usando o
sqlite3_open(":memory:", &db);.

Na opnião de vocês, qual a melhor abordagem? Caso seja a primeira qual
o melhor contêiner STL?

Obrigado!

[Thiago R. Adams]

A primeira coisa que você deve fazer é um teste de performance
chamando direto a função do sqlite.
Colocar num vector poderia ficar até mais lento.

Não é possível dizer o que é melhor se um vector ou set se você não
informar que tipo de operações quer fazer.


2008/10/6 Andre Duarte <clint.te...@gmail.com>:

[P.]

On 6 out, 15:54, Andre Duarte <clint.tecnolo...@gmail.com> wrote:

> 1- Carregar as tabelas em alguma* estrutura de dados, neste caso não
> sei qual contêiner seria melhor já que vou fazer somente
> consultas(read-only). vector<T>?? Sets<T>??
>
> 2 - Fazer um dump das tabelas do disco para a memória usando o
> sqlite3_open(":memory:", &db);.
>
> Na opnião de vocês, qual a melhor abordagem? Caso seja a primeira qual
> o melhor contêiner STL?

Se fosse possível escolher uma estrutura de dados ideal para a tarefa
de "consultar dados" a prática de desenvolvimento de sistemas seria
muitíssimo mais simples do que é hoje.
Atualmente, não se conhece uma estrutura de dados que seja ótima para
todos os cenários de "consultar dados".

Um especialista tomará esta decisão avaliando a forma da origem de
dados, a forma das consultas realizadas pelo sistema, as
características de desempenho do sistema etc.
Sem conhecimento desses detalhes não se pode dizer nem mesmo se
carregar as tabelas na memória é uma boa idéia.

Não existe tamanho único.

--
P.

[Rodrigo Strauss]

Faça os testes, mas vou te adiantar: SQLite é lento. Eles usam aquelas desculpa de que não é lento, que você que deveria usar transações para agrupar os comandos, mas muitas vezes você não pode fazer isso...

Eu faço tudo em memória usando STL, é bem rápido e eficiente. Teste o std::map e o stdext:hash_map. Teste o boost::multi_index, ele é bem rápido também.

Rodrigo Strauss

2008/10/6 Andre Duarte <clint.te...@gmail.com>

[Andre Duarte]

Primeiramente obrigado pela ajuda!

Preciso fazer buscas nas tabelas, só isso.

On 6 out, 15:59, "Thiago R. Adams" <thiago.ad...@gmail.com> wrote:
> A primeira coisa que você deve fazer é um teste de performance
> chamando direto a função do sqlite.
> Colocar num vector poderia ficar até mais lento.
>
> Não é possível dizer o que é melhor se um vector ou set se você não
> informar que tipo de operações quer fazer.
>

> 2008/10/6 Andre Duarte <clint.tecnolo...@gmail.com>:

[Thiago R. Adams]

Que tipo de busca?
Chave - valor?

Este seria o caso de usar um std::map
Mas se for fazer consultas acho que não vale a pena. A não ser que
você tenha algo muito específico.



2008/10/6 Andre Duarte <clint.te...@gmail.com>:

[Gianni]

On Monday 06 October 2008 15:54:44 Andre Duarte wrote:
> Como um dos requisitos do sistema é DESEMPENHO, necessito carregar
> estas tabelas em memória para agilizar as consultas, para isso tenho
> dois cenários:

Se vc quer desempenho, STL containers são sim mais rápidos que SQLite. A
única coisa que SQLite vai oferecer é quantidade recursos. Mas se você
prefere fazer na mão ao invés de usar SQL, não há dúvida: STL vai ser mais
rápido, sempre.

[P.]

On 6 out, 16:18, Gianni <nasus.maxi...@gmail.com> wrote:

> Se vc quer desempenho, STL containers são sim mais rápidos que SQLite.  A
> única coisa que SQLite vai oferecer é quantidade recursos.  Mas se você
> prefere fazer na mão ao invés de usar SQL, não há dúvida: STL vai ser mais
> rápido, sempre.

Considere as duas seguintes consultas:

1) SELECT COUNT(*) FROM start;

2) SELECT
start.start_sec,start.start_nsec,finish.ru_sec,finish.ru_nsec FROM
start LEFT JOIN finish ON start.pid = finish.pid;

Tirei estas duas consultas de uma única aplicação, com alguns ajustes
para tornar a consulta mais clara.

Você acha que, para todos os contâineres da STL, carregar os dados
implícitos nessas consultas dentro desse contâiner e substituí-las
pela execução de algum algoritmo apropriado tornará a aplicação mais
rápida, sempre?

--
P.

[Gianni]

On Monday 06 October 2008 16:30:07 P. wrote:
> Considere as duas seguintes consultas:
>
> 1) SELECT COUNT(*) FROM start;
>
> 2) SELECT
> start.start_sec,start.start_nsec,finish.ru_sec,finish.ru_nsec FROM
> start LEFT JOIN finish ON start.pid = finish.pid;
>
> Tirei estas duas consultas de uma única aplicação, com alguns ajustes
> para tornar a consulta mais clara.
>
> Você acha que, para todos os contâineres da STL, carregar os dados
> implícitos nessas consultas dentro desse contâiner e substituí-las
> pela execução de algum algoritmo apropriado tornará a aplicação mais
> rápida, sempre?

Todo não. Mas que usando STL containers isso pode ser faito mais rápido que
SQLite, isso eu tenho certeza.

Eu não disse que *qualquer* container sempre será mais rápido que SQLite.
Disse que "STL vai ser mais rápido, sempre". Óbviamente, é preciso usar o
container certo.

[Andre Duarte]

Por exemplo, tenho varias tabelas com duas colunas (particula e
padrao), uma operação muito comum é buscar por uma partícula e obter o
padrão.

paticula padrao
---------------------------------
...
rua r
avenida av
....

Tks

On 6 out, 16:17, "Thiago R. Adams" <thiago.ad...@gmail.com> wrote:
> Que tipo de busca?
> Chave - valor?
>
> Este seria o caso de usar um std::map
> Mas se for fazer consultas acho que não vale a pena. A não ser que
> você tenha algo muito específico.
>

> 2008/10/6 Andre Duarte <clint.tecnolo...@gmail.com>:

[Andre Duarte]

Rodrigo,

A STDEXT é portável e estável?

[]´s

On 6 out, 16:12, "Rodrigo Strauss" <rodr...@1bit.com.br> wrote:
> Faça os testes, mas vou te adiantar: SQLite é lento. Eles usam aquelas
> desculpa de que não é lento, que você que deveria usar transações para
> agrupar os comandos, mas muitas vezes você não pode fazer isso...
>
> Eu faço tudo em memória usando STL, é bem rápido e eficiente. Teste o
> std::map e o stdext:hash_map. Teste o boost::multi_index, ele é bem rápido
> também.
>
> Rodrigo Strauss
>

> 2008/10/6 Andre Duarte <clint.tecnolo...@gmail.com>

[Thiago R. Adams]

Neste caso você pode usar um std::map.
E poderia comparar a performance com um vector ordenado e contra um
unsorted map.


2008/10/6 Andre Duarte <clint.te...@gmail.com>:

[Andre Duarte]

> Se fosse possível escolher uma estrutura de dados ideal para a tarefa
> de "consultar dados" a prática de desenvolvimento de sistemas seria
> muitíssimo mais simples do que é hoje.
> Atualmente, não se conhece uma estrutura de dados que seja ótima para
> todos os cenários de "consultar dados".
>
> Um especialista tomará esta decisão avaliando a forma da origem de
> dados, a forma das consultas realizadas pelo sistema, as
> características de desempenho do sistema etc.
> Sem conhecimento desses detalhes não se pode dizer nem mesmo se
> carregar as tabelas na memória é uma boa idéia.
>
> Não existe tamanho único.

P,

Concordo com seu ponto de vista, devo admitir que estou mais inclinado
a efetuar
testes com os containers e com o Sqlite e ver qual se comporta
melhor.

Acho que uma abordagem melhor seria fazer o sistema usando os
containers que
achar melhor e depois, somente depois, fazer um profile para
identificar gargalos e
nestes pontos específicos testar outras abordagens.

[]´s

[Alain M.]

Gianni escreveu:

Só se as tabelas são pequenas.

Se as tabelas forem realmente grandes, você deveria usar uma árvore
binária equilibrada: AVL Tree
http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html
http://www.stanford.edu/~blp/avl/
http://www.strille.net/works/media_technology_projects/avl-tree_2001/

Alain

[Rodrigo Strauss]

Tem no GCC (talvez em outro namespace) e no Visual C++. *Acho* que não é padrão ISO.

Rodrigo Strauss

2008/10/6 Andre Duarte <clint.te...@gmail.com>

[Hugo Parente Lima]

std::map do GCC usa árvore preto-vermelho, que é uma árvore balanceada, porém
ela ainda é bem mais lenta que tabelas hash O(log(n)) vs O(1).

Você poderia usar as classes de tabelas hash que o google disponibilizou[1],
são 2, uma otimizada para economia de memória e outra para velocidade.

[1] http://code.google.com/p/google-sparsehash/

> Alain
>
> --~--~---------~--~----~------------~-------~--~----~
> C/C++ Brasil - http://www.ccppbrasil.org/
> Para sair dessa lista, envie um e-mail para
> ccppbrasil-...@googlegroups.com Para mais opções, visite
> http://groups.google.com/group/ccppbrasil
> --~--~---------~--~----~------------~-------~--~----~
> Campo de emprego & carreira: vag...@ccppbrasil.org
> http://groups.google.com/group/dev-guys?hl=en
> -~----------~----~----~----~------~----~------~--~---

--
Hugo Parente Lima
"Precisamos de mais gênios humildes no mundo, hoje somos poucos!"
JID: hu...@jabber.org

[Alain M.]

me ocorre uma outra idéia, que é a mais rápida de todas: carrega tudo na
memória com *matrizes*, faz um qsort ou já traz na ordem. Depois você
usa bsearch, acho que não existe coisa mais rápida, principalmente se o
índice for um int como parece...

é meio força bruta, mas que disse que com um canhão não se mata moscas.
(se não estiver dentro de casa :) )

Alain

Gianni escreveu:

[Pedro d'Aquino]

eu concordo com o P. que para alguns tipos de query, não necessariamente SQL será mais lento. Os bancos de dados são otimizados ao extremo tendo em vista o desempenho, e me parece um pouco ingênuo achar que uma solução mais rápida é simples. pode até ser possível (porque você poderia otimizar tudo para as >suas< queries), mas acho que o tamanho do problema pode vir a ser colossal - dependendo da complexidade das suas consultas...

maaas, a query que você usou de exemplo é extremamente simples. nesse caso acho que você consegue sim um ganho bem significativo botando tudo em memória e usando containers e algoritmos da STL.

deixo, humildemente, uma sugestão: meça, meça e meça, constante e metodicamente - é o único jeito de você comparar os méritos relativos das diferentes abordagens.

2008/10/6 Alain M. <ala...@pobox.com>

[Felipe Goron Farinon]

Não sei se o stdext:: é padrão, caso tu fores usar o stdext::hash_map
ao invés disso pode-se usar o std::tr1::unordered_map que utiliza
hashs para armazenar as chaves.

2008/10/6 Pedro d'Aquino <bud...@gmail.com>:

--
- Felipe Farinon

[Felipe Magno de Almeida]

2008/10/8 Felipe Goron Farinon <felipe....@gmail.com>:

>
> Não sei se o stdext:: é padrão,

Não é padrão.

> caso tu fores usar o stdext::hash_map
> ao invés disso pode-se usar o std::tr1::unordered_map que utiliza
> hashs para armazenar as chaves.

[snip]
--
Felipe Magno de Almeida

[P.]

On 8 out, 00:08, "Felipe Goron Farinon" <felipe.fari...@gmail.com>
wrote:

> Não sei se o stdext:: é padrão, caso tu fores usar o stdext::hash_map
> ao invés disso pode-se usar o std::tr1::unordered_map que utiliza
> hashs para armazenar as chaves.

Este namespace não é padrão.
Apenas std é padrão.

O próprio std::tr1 não é exatamente "padrão" mas parte de um
"technical report".
Implementar este "technical report" não é mandatório; std::tr1 possui
um nível de portabilidade menor que std.

--
P.

[Andre Duarte]

Pessoal,

Inicialmente vou fazer a app com o Sqlite em memória e analisar o
comportamento.
Caso o desempenho não seja aceitável em alguns pontos, especificamente
nestes
pontos eu parto para uma abordagem "braçal" usando containers STL ou
BOOST já
que uma das premissas tb é portabilidade.

Muito obrigado a todos pela ajuda. Pelo que pude perceber o nível aqui
é bem melhor
do que no "C/C++ Programmer's Group" apesar de não ter postado a
dúvida lá.

[]´s

[rodrigo...@gmail.com]

Lembrei disso, http://datadraw.sourceforge.net/