Como isso é possível???

A um bom tempo venho reunindo uma blacklist de sites mal intencionados, ads, ponográficos, e etc... O arquivo que tenho hoje está implementado em um servidor squid que bloqueia todos os sites do mesmo...

O arquivo que tenho hoje tem exatamente 2017096, sim isso mesmo, 2 milhões de sites!

Ao iniciar o servidor, ele leva cerca de 13~15 segundos para ler o arquivo e ficar online... mas isso não é o que me intriga.

Para bloquear os sites o squid precisa ler a url que você digitou e comparar com a blacklist certo? E todas as páginas que acesso são identificadas quase que instantaneamente...

Como é possível um programa comparar a string com uma blacklist de 2 milhões de sites instantaneamente???

Isso é surreal pra mim!

Imagine como o Google faz então :-)

Como achar o que você procura nas Goooooooooooooogleeeeeee páginas que existem pela internet??


"Google significa um número muito grande" (Larry Page)

acho que um dos meio para se fazer isso é ordenando a lista e fazer marcas para ele localizar uma possível ocorrência mais rapidamente, assim ele pega a primeira letra do site e vai direto ate a marca da letra e assim suscetivamente ate um ponto em que esse método seja muito custoso e é trocado por outro método que trabalhe melhor com pequenas quantidade

Que tal pensar no modo SQL da coisa?

É por isso que eu acho algo patético esse consumismo de hardware hoje em dia. Um processador faz muitos calculos em muito pouco tempo e ninguém tira proveito disso. É preferível (povinho da preguiça) programar em linguagens de alto nivel que jogam bibliotecas inteiras na memória para executar um hello world de 14KB do que usar um assembly que pesa menos de 1Kb que diz hello world e ainda recita o lema da ONU.

Os Sres. não tem ideia do que um processador de 10MHz é capaz de fazer, imagine então um de 3GHz!?

@rai3mb Nossa! É incrível, mas nunca havia pensado nisso kkk

Tenha medo do google O.O

@fabricio.er É uma boa opção, mas mesmo assim não pode ser...
Não tenho como obter essa informação, mas deve ter no minimo umas 50 mil linhas de cada letra, isso sem contar os ips...

@ThePinkShark Pois é.... sql.... já tenho o que fazer hoje *.*

mrk3004

se consideramos que tenha apenas letras e numeros no começo do endereço bloqueado teremos 2000000/36 que da 55555.56 e se usarmos o método novamente o numero cai para 1543.20 e uma terceira vez 42.86 é claro que essa alternativa seria uma [*****] se precisássemos ordenar a lista toda vez.

sei disso pq fiz um programa em python para achar os números primos ate 2 milhões(sei que python não é a melhor alternativa mas no momento é a única linguagem que sei trabalhar) e vi que no pc que eu estava poderia demorar muito para terminar ele então eu otimizei primeiro gerando a lista de 2 em 2 e depois eliminando os múltiplos de 3 baseado no fato que eles aparecem a cada 4 números na lista e mesmo assim demorou muito

Bom no caso da Google, os servidores devem ser poderosos.
acho isso, pq vejam o email da google, o GMail. Eles estão dando 8 giga
de espaço para cad usuário.
fico imaginando o tamanho dos servidores, pq há zilhões de usuários de GMail
e centenas ou mesmo milhares de novos usuários por dia, no mundo todo.

Não entendo nada dessas coisas, mas gosto de ler o assunto.
Vi numa Info/2010 uma matéria sobre o sistema de busca do Google. O chamado 'Algotitmo de busca'.
Um dos engenheiros(sim, é isso) dessa área é um mineiro do escritório/filial do Google em Belo Horizonte. Nas época eles estavam em busca de pessoas formadas em T.I. mas com habilidades matemáticas para entrar na turma.

De lá pra cá, o sistema de busca do Google evoluiu e chegou ao 'Instant Search': http://www.youtube.com/watch?v=RqLrJi-iPEA

Tudo isso é muito loko!

NO caso do Gmail é fácil de imaginar a tática, muito provavelmente mostram que você tem 100MB ocupados baseado no conteúdo dos seus e-mails reais, mas o que de fato fica armazenado é uma compressão dos mesmos.

Sabemos que arquivo texto tem uma taxa de compressão alta, então se seus e-mails ocupariam 1GB em um HD, o Google informa isso para você, mas o que ocupa na realidade é apenas alguns Megas.

Claro, tem diversos outros aspectos, como processamento e acesso à disco (I/O), mas isso é outra história :-)

No caso do problema do nosso amigo acredito que usam algoritmo de busca bem aprimorado, como o método de pesquisa binária, peguei um livro da universidade com código em Pascal e adaptei para o shell, vejam um exemplo:
--------------------------
#!/bin/bash
BUSCA=$1

#Elementos
VALORES=(1 3 5 7 9 10 11 12 13 14 15 18 19 32 45 67 71 72 73 75 76 79 80 82 85 199 345 500 545 651 678 745 867 987 988 989 999)

INICIO=1
FINAL=$(echo "${#VALORES[@]}")
FINAL=$(($FINAL-1))

i=0
while [ $INICIO -le $FINAL ]
do
MEIO=$((($INICIO+$FINAL)/2))
if [ ${VALORES[$MEIO]} -eq $BUSCA ]; then
echo 'achou'
break;
elif [ $BUSCA -gt ${VALORES[$MEIO]} ];then
INICIO=$(($MEIO+1))
else
FINAL=$(($MEIO-1))
fi
i=$(($i+1))
done

echo "Quantidade de Elementos: ${#VALORES[@]}"
echo "Elemento que buscamos: $BUSCA"
echo "Quantidade de iterações: $i"
---------------------------------------------

Obs.: Os elementos devem está ordenados.

Agora vem um exemplo de resultado:
./buscaBinaria.sh 67
achou
Quantidade de Elementos: 37
Elemento que buscamos: 67
Quantidade de iterações: 3


Vejam que precisou de apenas 3 iterações, sendo que temos 37 elementos para buscar, então podemos imaginar que mesmo se tivermos milhões de registros, a busca será reduzida drasticamente, usando um método como esse.

Abraços

Usando busca binária por exemplo pode-se achar um n° numa lista(ordenada) de 2 milhões de números com no máximo 21 tentativas!(que é a potência de 2 mais próxima*). Esses algoritmos são fantásticos mesmo. :-)

*2^21 = 2 097 152 (eu acho. rsrs)

Agora eu entendi porque o google deu tão certo... é muito legal de estudar e mexer com esses algorítimos de busca, são fantásticos!!! Eu ainda não tinha tido contato com essa parte, to lendo uns materiais que encontrei aqui e poxa, é tão fantástico que chega ser até divertido haha.

Eu já achava as coisas que o google faz eram incríveis, mas depois disso não sei nem definir mais. As pessoas fazem buscas naquele pequeno textbox do google e nem imaginam o que tem por trás disso. Eu nunca parei pra pensar nessa questão da quantidade de dados e a velocidade de resposta da busca... poxa, deve ser incrível a engine por trás desse buscador.

Eu encontrei uma apostila da unicamp que fala um pouco sobre o assunto goo.gl/AtZ9N .

Agora não vai ter jeito, não vou sossegar enquanto não conseguir criar um buscador eficiente.

Droga! =(