Nas partes anteriores ...
Q: o que temos?
A: Estatísticas coletadas dos hosts.
P: O que queremos obter?
A: Topologia de rede! Mais precisamente, você precisa criar a cadeia correta de pares (hosts) para o RingSync .
Temos que criar um algoritmo que primeiro transforme as estatísticas em uma topologia de rede e depois em uma cadeia de pares. Até agora, o algoritmo se parece com isso:
–-[**]--> --[**]-->
Se você gostou de ler a "Parte 1" nas páginas do GitHub , aqui está um link para essa parte nas páginas do GitHub.
Aviso : Abaixo estarão os mesmos artefatos Habr-parser que eu avisei na "Parte 1" .
Nota : além disso, em vez de “ –-[**]--> ” usarei “ –-[???]--> ”.
As estatísticas coletadas nos mostram em quais hosts a velocidade de recebimento do tráfego de transmissão caiu. Por exemplo, observe o resultado da iteração zero na rede "N2_2" (" Network " do artigo anterior "LLTR Parte 1"):
{300,164,164},
2 estados anfitriões são claramente visíveis aqui:
- velocidade normal (valor “
300 ”) - sem reação ; - a velocidade caiu (valor "
164 ") - há uma reação .
No que estou chegando? À binarização! Se codificarmos a ausência de uma reação como 0 e a presença de uma reação como 1 , podemos colocar todas as reações dos hosts em uma única iteração em uma variável ( 32 - 512 bits [ AVX - 512 ]). Além de economizar memória (e espaço gasto em caches), isso aumentará a velocidade do processamento - todas as respostas do host de uma iteração específica ( SIMD ) serão processadas de uma só vez em uma instrução.
Nota : porque usar o LLTR Basic para um grande número de hosts é muito caro ( consulte o início da seção “LLTR Part 0 :: LLTR Advanced” ), então tudo se encaixa nos registros x86‑64 de 64 bits .
Nota : No texto do link da seção localizada em outro artigo (outra parte), adicionarei o número da peça no formato: “ LLTR Part # :: ‹ nome da seção › ”. E no " title " do link, anotarei o nome da peça, por exemplo, para "LLTR Part 0 ::", "Detectar automaticamente a topologia de rede e os switches não gerenciados aparecerão". Missão impossível?
Vamos pegar o mesmo exemplo de iteração zero e ver como ficará a binarização:
{300,164,164} --[]--> 011
Muito compacto, mas eu gostaria que “ 1 ” (a presença de uma reação ) chamasse minha atenção imediatamente ao exibir uma lista de todas as iterações. Agora " 1 " não se destaca no contexto " 0 " (dados falsos, para um exemplo visual ):
0101011010110 1100010110010 0101101010111 0100010110100
Para destacar " 1 ", apresento a notação:
- "
1 " significa 1 - há uma reação ; - "
. Significa 0 - sem reação .
Vejamos os "dados falsos" novamente:
.1.1.11.1.11. 11...1.11..1. .1.11.1.1.111 .1...1.11.1..
Muito melhor ( IMHO ).
O algoritmo, no momento, fica assim:
–-[]--> --[???]--> --[???]-->
Deixamos os detalhes da binarização para o final do artigo e nos concentramos no restante do algoritmo.
É mais fácil criar um algoritmo baseado em dados de entrada / entrada específicos (casos especiais, condições de contorno; testes em termos de TDD ). No nosso caso, os dados iniciais dependem da topologia da rede, portanto, é necessário criar uma rede que seja pequena e, ao mesmo tempo, contenha esquemas de conexão de comutador diferentes ( estrela , conexão serial ). Talvez algo especial possa ser incluído nela ... Em geral, a imaginação desenhou uma rede assim (a notação para os elementos é semelhante à notação usada no final da seção " LLTR Parte 0 :: Topologia:" conexão serial de comutadores " "):
Nota : olhando para esta rede, a pergunta “é possível realizar uma varredura completa nesta topologia se um dos comutadores ...” (próximo ao final da seção “ LLTR Parte 0 :: Topologia:“ conexão serial de comutadores ” ”) e você percebe que nenhum host está diretamente conectado a um dos comutadores. Além disso, não há problemas, porque Mais 3 comutadores estão conectados a esse comutador (contei apenas os comutadores conectados "de baixo", sem levar em conta o fato de que ele está conectado a outro comutador "de cima"), cada um com hosts.
No entanto, neste diagrama, existem alguns detalhes extras (perturbadores). Vou limpá-lo removendo:
- host de transmissão (não está na entrada / estatística);
- portas que conectam comutadores entre si.
Aqui a opção "sem hosts" é imediatamente visível. Além disso, organizei todos os comutadores de forma que os hosts neles não se sobreponham verticalmente. Isso será útil se, no futuro, eu quiser mostrar "reações do host" não na forma de uma entrada de texto " .....1...... ", mas na forma de um diagrama (existe apenas um host em uma vertical):
Agora imagine as estatísticas que obtemos ao final de todas as iterações de varredura nesta rede. Existem 12 hosts na rede (excluindo host de transmissão), portanto, teremos dados em 132 iterações. No entanto, nem todos os resultados da iteração serão úteis para nós, por exemplo, serão inúteis:
Após a limpeza, de todos os 132 resultados da iteração, apenas 5 (respostas do host) permanecerão:
1111111111.. 11111111.... ..111....... .....111.... 11..........
Nota : para maior clareza, organizei as iterações na ordem de um número maior de “ 1 ” para um menor.
O algoritmo começou a ficar assim:
–-[]--> --[ ]--[ ]--[???]--> --[???]-->
ponto de reset
Pensei em incluir tudo isso no spoiler, mas no final percebi que essa é uma parte importante da história, que é melhor não perder ao ler.
¬ ( Não pule para o cérebro ao ler : Cong
[ponto de redefinição] Nos 5 resultados restantes da iteração, os dois primeiros chamam a atenção: o primeiro inclui o segundo e o segundo inclui os 3 restantes. Aqui me lembro da “sombra” da seção “ LLTR Part 0 :: Topology:“ conexão serial de switches ” ”. Na mesma seção, no final de cada iteração, formamos (ou não) novos clusters com base nos dados recém-obtidos. Agora precisamos fazer o mesmo.
Mas como formamos novos agrupamentos? De fato, todas as reações (não únicas) dos hosts " 1 " da iteração atual foram o "novo cluster", apenas tivemos que encontrar as interseções ("∩"; não "empty" vazio)) com os clusters existentes para remover ("∖") dos maiores hosts de cluster incluídos em um cluster menor.
No entanto, em nossas ações houve uma condição / ramificação (se): você precisa determinar qual dos clusters é maior e, em seguida, executar uma operação simples (A ∖ B) - subtrair o menor (B) do cluster maior (A). Representando o tormento de uma CPU com um pipeline longo causado pela necessidade de redefinir o pipeline se a previsão de ramificação estiver incorreta (se houver um "bloco de previsão de ramificação"), eu quase decidi usar o “?: " , Mas naquele momento ...
Eu fiquei no banheiro e pendurei o relógio. De repente, escorregou, bateu a cabeça na pia e, quando acordei, tive uma visão, uma imagem no meu cérebro, uma visão disso - um separador de fluxo de unidade de fluxo ( De volta ao futuro ) :
E veja imediatamente seu trabalho no exemplo de clusters sobrepostos (mais precisamente, um conjunto (cluster) é estritamente incluído " " em outro conjunto):
.....11..... - a ..11111111.. - b ..111..111.. - c=a^b ............ - aa=a&c ..111..111.. - bb=b&c .....11..... - cc=a&b
Clusters disjuntos:
..111....... - a .......111.. - b ..111..111.. - c=a^b ..111....... - aa=a&c .......111.. - bb=b&c ............ - cc=a&b
Acontece que:
- "
aa " contém elementos exclusivos de " a "; - em "
bb " - exclusivo para " b "; - em "
cc " - comum a " a " e " b ".
Outro exemplo com clusters cruzados ("impossível", mas um bom exemplo):
...1111..... - a .....1111... - b ...11..11... - c=a^b ...11....... - aa=a&c .......11... - bb=b&c .....11..... - cc=a&b
Nota : esse tipo de resposta (reação do host) não está nos dados de origem.
Da mesma forma, você pode se livrar das tomadas :
.....11..... - a .....11..... - b ............ - c=a^b ............ - aa=a&c ............ - bb=b&c .....11..... - cc=a&b
Mas um pouco mais tarde ...
A cabeça deixa de doer depois de bater na pia, a mente limpa e surgem problemas óbvios ...
Na entrada, temos 2 variáveis (resultados da iteração / reações do host / clusters / conjuntos / ...), mas já existem 3 na saída e pelo menos uma delas estará vazia ("∅"). Se você não se livrar imediatamente de "∅", precisará incluí-los no processamento no futuro. Portanto, é melhor se livrar do "∅" imediatamente. Mas como fazer isso? Use condição / ramificação! ... Em geral, voltei para onde comecei. Além disso, se tudo for feito conforme descrito acima, além de eliminar ",", no final, obtemos:
1111111111.. 11111111.... ..111....... .....111.... 11..........
Isto é:
........11.. - "............", ：（ ..111....... .....111.... 11..........
É hora de fazer a pergunta: "Como obter a topologia de rede com isso?" Agora, esses dados podem "dizer" sobre qual cluster um host específico pertence (ou seja, a qual comutador o host está conectado), mas esses dados agora carecem completamente de informações sobre a topologia dos comutadores (ou seja, como estão conectados alterna entre si) - perdemos essas informações durante a conversão de dados. Além disso, a qual cluster (switch) os 2 hosts mais à direita pertencem? Se considerarmos cada linha como um cluster separado (ou como uma indicação de quais hosts estão conectados a um comutador específico), acontece que esses dois hosts extremos não estão conectados a lugar algum! Além disso, temos 6 comutadores na rede e restam 4 linhas, onde existem mais 2 linhas? Nós apagamos um (como diz o comentário acima) e, no outro, deveria haver "2 hosts na extrema direita".
[ ir ao ponto de redefinição ] Para desenvolver ainda mais essa idéia, é inútil. Sem saída (ramo git). Você terá que reverter para o rótulo "ponto de redefinição", esquecendo tudo o que estava atrás dele, mas deixando esse ramo para a história.
Agora, para não cair em mais um "ramo morto", você precisa decidir sobre a estrutura final (representação) da topologia de rede na memória. Ou seja, com o que queremos obter no momento da "topologia de rede":
–-[]--> --[ ]--[ ]--[???]--> <strong> </strong> --[???]-->
Primeiro , todos os hosts devem estar presentes:
<strong>..........11</strong> <-- 1111111111.. 11111111.... ..111....... .....111.... 11..........
Em segundo lugar , os pais devem ser indicados (o cluster pai de cada cluster; no momento: pai ⊋ filho ; no diagrama de rede, coloquei os pais acima dos filhos) (os números do cluster são adicionados à esquerda):
0) ..........11 parent: ? 1) 1111111111.. parent: ? 2) 11111111.... parent: 1 3) ..111....... parent: 2 4) .....111.... parent: 2 5) 11.......... parent: 2
Nota : se você notar algo estranho aqui, comparando o diagrama desta rede com esses dados, então você gosta de mim.
Spoiler, é melhor não abrir até ler a lista inteira
De fato (de acordo com o diagrama), o pai do cluster 1 é o cluster 0, mas a condição " pai ⊋ filho " não é cumprida. Talvez em " First " tenhamos cometido um erro, e em vez de " ..........11 " valesse a pena adicionar " 111111111111 "?
Terceiro , deve haver um pai "raiz" ligando árvores individuais (ou seja, floresta ) em uma árvore:
-1) 111111111111 0) ..........11 parent:-1 1) 1111111111.. parent:-1 2) 11111111.... parent: 1 3) ..111....... parent: 2 4) .....111.... parent: 2 5) 11.......... parent: 2
Em quarto lugar , seria bom ter listas de filhos com cada pai:
-1) 111111111111 children: 0,1 0) ..........11 parent:-1 1) 1111111111.. parent:-1, children: 2 2) 11111111.... parent: 1, children: 3,4,5 3) ..111....... parent: 2 4) .....111.... parent: 2 5) 11.......... parent: 2
E , finalmente , agora é possível excluir filhos de seus pais:
-1) ............ children: 0,1 0) ..........11 parent:-1 1) ........11.. parent:-1, children: 2 2) ............ parent: 1, children: 3,4,5 3) ..111....... parent: 2 4) .....111.... parent: 2 5) 11.......... parent: 2
Agora, cada linha descreve um cluster, ou seja, aponta para hosts conectados ao mesmo switch. No entanto, espere, existem 6 comutadores em nossa rede e 7 clusters! Finalmente, chegou a hora de ler o texto do spoiler acima de " Spoiler, é melhor não abrir até ler a lista inteira " e corrigir a situação:
0) ..........11 children: 1 1) ........11.. parent: 0, children: 2 2) ............ parent: 1, children: 3,4,5 3) ..111....... parent: 2 4) .....111.... parent: 2 5) 11.......... parent: 2
Esses dados são precisamente a "topologia de rede" - descrevem a árvore dos comutadores e, a partir dele, é possível determinar todos os hosts conectados a um comutador específico.
–-[]--> --[ ]--[ ]--[???]--> <strong> </strong> --[???]-->
Resta entender como trazer os dados para este formulário. De fato, tudo o que fizemos (em primeiro lugar, em segundo lugar, ...) pode ser convertido em um algoritmo:
- “Primeiramente” (depois de fazer as correções do spoiler, ele se torna semelhante à ação “terceirizada”) - adicione um cluster “raiz” “
111111111111 ” ( universal ), incluindo (hosts de todas as árvores da floresta ∪ hosts localizados no mesmo switch que o host de transmissão ), ou seja, Inclui todos os hosts na rede; - “Secondly” - procure um pai para cada cluster ;
- “Quarto” - construindo uma lista de filhos para cada pai ;
- "E finalmente" - a exclusão dos filhos dos pais .
Agora você pode adicionar essas ações ao algoritmo geral (mudou ligeiramente a aparência):
● ● [] ► [ ] [ ] ► / [ "" ] ► / [ ] [ ] [ ] ► ● [???] ► ●
Vista alternativa
● ► [] ▬ ► [ ] [ ] ▬ / ► [ "" ] ▬ / ► [ ] [ ] [ ] ● ► [???] ● ●
Vamos ver o que acontece se você aplicar esse algoritmo a outra rede. Gostaria de pegar a rede Network_ serial e seus resultados de simulação (estatísticas) da seção “ LLTR Parte 1 :: Mais redes com topologias diferentes, adicionando novas redes ”.
Nota : Por que eu escolhi essa rede específica? É muito grande e existem falhas nos dados coletados (consulte o final do spoiler "Resultados da simulação" para esta rede).
Vamos lá!
Binarização
Reações do Anfitrião:
.111111.. .111111.. .111111.. .111111.. .111111.. .111111.. .......11 .......11 ..1...... ...1111.. ...1111.. ...1111.. ...1111.. .......11 .......11 1........ ...1111.. ...1111.. ...1111.. ...1111.. .......11 .......11 1........ .1....... ....1.... .....11.. .....11.. .......11 .......11 1........ .1....... ..1...... .....11.. .....11.. .......11 .......11 1........ .1....... ..1...... ...1..... ......1.. ......... ......... ......... .1....... ..1...... ...1..... ....1.... ......... ......... ......... .1....... ..1...... ...1..... ....1.... .....1... ........1 1........ .111111.. .111111.. .111111.. .111111.. .111111.. .111111.. 1........ .111111.. .111111.. .111111.. .111111.. .111111.. .111111.. .......1.
Purificação de reações únicas
.111111.. --> .111111.. .111111.. --> .111111.. .111111.. --> .111111.. .111111.. --> .111111.. .111111.. --> .111111.. .111111.. --> .111111.. .......11 --> .......11 .......11 --> .......11 ..1...... --> ...1111.. --> ...1111.. ...1111.. --> ...1111.. ...1111.. --> ...1111.. ...1111.. --> ...1111.. .......11 --> .......11 .......11 --> .......11 1........ --> ...1111.. --> ...1111.. ...1111.. --> ...1111.. ...1111.. --> ...1111.. ...1111.. --> ...1111.. .......11 --> .......11 .......11 --> .......11 1........ --> .1....... --> ....1.... --> .....11.. --> .....11.. .....11.. --> .....11.. .......11 --> .......11 .......11 --> .......11 1........ --> .1....... --> ..1...... --> .....11.. --> .....11.. .....11.. --> .....11.. .......11 --> .......11 .......11 --> .......11 1........ --> .1....... --> ..1...... --> ...1..... --> ......1.. --> ......... --> ......... ......... --> ......... ......... --> ......... .1....... --> ..1...... --> ...1..... --> ....1.... --> ......... --> ......... ......... --> ......... ......... --> ......... .1....... --> ..1...... --> ...1..... --> ....1.... --> .....1... --> ........1 --> 1........ --> .111111.. --> .111111.. .111111.. --> .111111.. .111111.. --> .111111.. .111111.. --> .111111.. .111111.. --> .111111.. .111111.. --> .111111.. 1........ --> .111111.. --> .111111.. .111111.. --> .111111.. .111111.. --> .111111.. .111111.. --> .111111.. .111111.. --> .111111.. .111111.. --> .111111.. .......1. -->
Limpeza de duplicatas (obtemos “aglomerados / floresta”):
.111111.. .......11 ...1111.. .....11.. .........
Além disso, por conveniência , classificarei em ordem decrescente a quantidade " 1 ":
.111111.. ...1111.. .....11.. .......11 .........
Nota : Pode valer a pena incluir a classificação no algoritmo. O que você acha?
Adicionando um cluster "raiz" (obtemos "clusters / tree"):
111111111 .111111.. ...1111.. .....11.. .......11 .........
Inclui hosts de 2 árvores (esquerda " .111111.. " e direita " .......11 " parte da rede) e 1 host (" 1........ " localizado em um alternar com o host de transmissão).
Pesquisa pai para cada cluster:
0) 111111111 1) .111111.. parent: 0 2) ...1111.. parent: 1 3) .....11.. parent: 2 4) .......11 parent: 0 5) ......... parent: 4
Nota : Foi aí que ocorreu o impacto negativo das lacunas de dados - o 4º cluster tornou-se o pai do 5º! Em geral, qualquer cluster pode se tornar o pai do 5º cluster, porque está vazio (∅).
Construindo uma lista de filhos para cada pai:
0) 111111111 children: 1,4 1) .111111.. parent: 0, children: 2 2) ...1111.. parent: 1, children: 3 3) .....11.. parent: 2 4) .......11 parent: 0, children: 5 5) ......... parent: 4
Exclusão de filhos dos pais:
0) 1........ children: 1,4 1) .11...... parent: 0, children: 2 2) ...11.... parent: 1, children: 3 3) .....11.. parent: 2 4) .......11 parent: 0, children: 5 5) ......... parent: 4
Nesta etapa, deveríamos obter uma "topologia de rede". E nós conseguimos. Se estamos interessados apenas na localização dos hosts, essa "topologia de rede" é bastante satisfatória para nós. No entanto, outro switch apareceu em nossa rede, no qual 0 hosts!
Para consertar tudo, basta uma das primeiras etapas para eliminar essas "falhas de dados". Isso pode ser feito imediatamente após a "binarização":
● ● [] ► [<strong> (∅), (⦱)</strong>] [ ] [ ] ► / [ "" ] ► / [ ] [ ] [ ] ► ● [???] ► ●
Excluímos conjuntos vazios (∅; “ ......... ”), mas por que remover universos (⦱; “ 111111111 ”)? A resposta ficará aparente quando começarmos a implementar a fase de "binarização". Diferentes variantes da implementação da “binarização” podem produzir “ ......... ” e “ 111111111 ” nos mesmos dados (dados com o defeito descrito). E porque é tão impossível obter “ 111111111 ” nos dados de entrada corretos quanto obter “ ......... ”, então podemos excluir todos os “ 111111111 ” (além disso, eles não carregam nenhuma informação, exceto que existem "falhas" nos dados).
Se você aplicar esse algoritmo (aumentado, corrigido) à mesma rede (" Network_ serial "), a "topologia de rede" será semelhante a esta:
0) 1........ children: 1,4 1) .11...... parent: 0, children: 2 2) ...11.... parent: 1, children: 3 3) .....11.. parent: 2 4) .......11 parent: 0
Nota : Bom, é a diagonal. , . , 2 ( “switch0”), 1 ( 2 ):
“ ”
0) 11........ children: 1,4 1) ..11...... parent: 0, children: 2 2) ....11.... parent: 1, children: 3 3) ......11.. parent: 2 4) ........11 parent: 0
0) 1...... children: 1,4 1) .1..... parent: 0, children: 2 2) ..1.... parent: 1, children: 3 3) ...11.. parent: 2 4) .....11 parent: 0
“ ”. “ ” “ ”. RingSync , ( : Pre‑order ). “ ” :
1 1........ hostS/seed -> host0 -> . .11...... host1 -> host2 -> . ...11.... host3 -> host4 -> . .....11.. host5 -> host6 -> . .......11 host7 -> host8/leech
Note : (, ) , broadcast .
, “ ” ( ), (“ Network_ serial ”). ( ), . :
, “ ” (“ ”):
..........11 1 hS/seed -> h10 -> h11 -> ........11.. . h8 -> h9 -> ..111....... . h2 -> h3 -> h4 -> .....111.... . h5 -> h6 -> h7 -> 11.......... . h0 -> h1/leech
( “ ”) . , – 2, .. (∅). , “ ” , “ ” ( , ), (∅) ? , : ‑, “” , ( , ；）; ‑, ( ).
, “ ”, …
Note : , , . .
, ( ), .
:
..........11 1 hS/seed -> <strong>h11</strong> -> <strong>h10</strong> -> ........11.. . <strong>h9</strong> -> <strong>h8</strong> -> ..111....... . h2 -> h3 -> h4 -> .....111.... . h5 -> h6 -> h7 -> 11.......... . h0 -> h1/leech
“ Network_ serial ”…
, :
switch0 -> switch1 -> switch2 -> switch3 -┐ switch4 <- switch0 <- switch1 <- switch2 <-----------┘
… “” “ switch0 <- switch1 <- switch2 ”. :
switch0 -> switch4 -┐ switch3 <- switch2 <- switch1 <- switch0 <-----------┘
:
, , , !
Note : , .. “ ”.
Note : “ ”, “ ” ( ; – L0 ) – .
, “ ” .
Note : , – .
() : “ ” ( LLTR 0:: : “ ” ) :
- – ;
- – ;
- – ( );
- – ( ) – , .
Note : “ – ” “ , ”, , , .
Note : – ( ). – ( ) . , ( ): ( ); ( ).
:
● ● [] ► [ (∅), (⦱)] [ ] [ ] ► / [ "" ] ► / [ ] [ ] [ ] ► ● [ /] ► ●
“ ” “ Network_ serial ” :
1 1........ hostS/seed -> host0 -> . .......11 host7 -> host8 -> . .11...... host1 -> host2 -> . ...11.... host3 -> host4 -> . .....11.. host5 -> host6/leech
“ ”, .
“ ” . “ ” :
s0) ..........11 1 hS/seed -> h10 -> h11 -> s1) ........11.. . h8 -> h9 -> s3) ..111....... . h2 -> h3 -> h4 -> s4) .....111.... . h5 -> h6 -> h7 -> s5) 11.......... . h0 -> h1/leech
? , , , ( ):
s0 -> s1 -> s2 -> s3 -┐ ┌- s4 <- s2 <------┘ └------> s2 -> s5
Note : “ s# ” “ ” (. ).
# TL;DR
:
- (~~ k‑medoids ~~) + (∅), (⦱) + :
a min a max- 2
- + (∅), (⦱)
- :
- ( : )
- ( O(nlogn) O(1) )
- ( nth_element implementations complexities )
a medL (medLow) a medR (medHi)- 2 ,
- +
- + “” :
- + “”
- +
bitCount ( max min)
- :
- min (min) (max) ( ) , ;
bitCount(a i )==bitCount(a i |a min ) , : a i ==a i |a min - , ( ) –
- min ( )
- () :
- ( “” “”)
- :
- “”, max , or|=a i ,
a max &=~or
( “ a max ^=or ” – )
( a max a min , .. , )
- /:
- (RingSync)
Note : 
, .
. ( ), .
“ , ”
, , (“ {…} ”) () . ():
“”, ():
, :
? TensorsFlowing
isto é – , “, ” – .
?
:
- – ( ) , . “” , .. “” “” . , “ ”, .
- – “” / , , . . , (Interprocedural optimization, Whole program optimization; Link‑time optimization) “” – .
Note : : .. (2D/3D , , *, …). (), , , ( , , 24 , ; , ACPI ), ( ) , ：（. (, , …) , ‑ . , , ‑. ( “” “”), “ *”. , – , , , . () – , . – ( ), . – , //‑/ /. (debug) ‑ .
Note : Debug , (, – { 9 , ; – ×16 ( 1.2 1.5); → }), warning' .
Note : , , , ‑. , , ( “ ” ) .
# Tooo Long; Didn't Read; Visualize, plz.
Note : , ( GIF “TensorsFlowing” “ ”). GIF “TensorsFlowing” GIF “ Loop over python list animation ”. , GIF , “ ” / . , ‑ 1:1, “ ”.
Note : GIF ( “Loop over python list animation”), . , , . ( ；）
Note : ( ) ( ). , .
Note : GIF ( “Scroll Down”) – (Ctrl+R), GIF . ( , ; , ‑ <oembed> ? )
#1
int average;{ int max,min; max=min=countFill[i][0]; for(int j=1;j<numHosts;j++){ max=countFill[i][j]>max?countFill[i][j]:max; min=countFill[i][j]<min?countFill[i][j]:min; } average=(max+min)/2; }
Note : GIF …
#2
int lo=0; struct CnN{ int Count; }iFill[numHosts]; for(int j=0,hi=numHosts-1;j<numHosts;j++){ if(countFill[i][j]<average) iFill[lo++].Count=countFill[i][j]; else iFill[hi--].Count=countFill[i][j]; } bitCluster[i]=0; if(lo==0||lo==numHosts) continue;
Note : ( ) .
#3
int averageMed;{ CnN *iFillLo=&iFill[0]; CnN *iFillHi=&iFill[lo]; const int hi=numHosts-lo; if(lo>1) std::nth_element(iFillLo,&iFillLo[lo/2],&iFillLo[lo],[](const CnN a,const CnN b){return a.Count<b.Count;}); if(hi>1) std::nth_element(iFillHi,&iFillHi[hi/2],&iFillHi[hi],[](const CnN a,const CnN b){return a.Count<b.Count;}); averageMed=(iFillLo[lo/2].Count+iFillHi[hi/2].Count)/2; }
Note : std::nth_element() , , ( + = ).
#4
for(unsigned int j=0;j<numHosts;j++) bitCluster[i]|=( (countFill[i][j]<averageMed)?1:0 )<<j;
#5
bitCluster[i] = bitCluster[i]^(1<<((i/(numHosts-1))+(i%(numHosts-1)+1))%numHosts) ? bitCluster[i]:0;
Note : GIF . ReadMe ( ; ‑ , ).
...
3‑ 1.92 , , 1.6 - 2 . , 3‑ ( ) ( Go – 2 , – 2 - 4 ). (4 ), 2.5 LLTR.
+ TODO' + .
, ‑ , , , 2 .
Note : , / , …
Spoiler
2 ?
# Tooo Long; Didn't Read; Visualize, plz.
TODO[old]: (1 – gif_1, , 2 – gif_2, , …)
TODO: ,
? ( )
TODO: ( GIF “TensorsFlowing”, ‑ – ),
( Note, GIF , , , YouTube. : 4:2:0 TV‑ ( 16 - 235 ). , – (). : SVG – , “ ‑”; SWF – RIP)
( ), std (, ) ( );
( “ 1 ” == “ 1 ” ). Um exemplo:
0) 111111111111 1) 1111111111.. 2) 11111111.... 3) ..111....... 4) .....111.... <- , 2‑, 3‑ 5) 11..........
(.. ), .. “ 1 ” ( ) (. “ ” “ ”). “ 1 ”, ..:
0) 111111111111 1) 1111111111.. 0 2) 11111111.... 1 3) ..111....... 2 4) .....111.... 2 5) 11.......... 4
( , – + (+), )
( “”). CPU, + . , , , , .
...
3: OMNeT++
LLTR 3: OMNeT++
Golang. ( , )
( , OMNeT++ c Qtenv)
( “background/fresh” “.ned” {“ grey99 ” → “ -,-,0;bgi=background/fresh ”}, “blueprint/print-26.png” Qtenv “LLTR 1:: ”)
( , “OMNetProject (v0.9) lltdapp”)
( , “hostS” – ( ) . , , – broadcast , unicast , .. – , . , – “ ”. “ – ”, : “ ” – “Serial” “ 1” ( – “ ”). – (, , broadcast unicast )[ rand , , – , – ])
( Precision Time Protocol (PTP) 2016-04-12)
( – , , “a3_v0.3_ft0.1.0”, “a3_v0.3.0” – , ; “ft” – fixed time)
.
TODO [x]: , , . “ TODO [x]” “ ” ( )
Referências:
4:
LLTR 4:
∀ habrauser ∈ {user ∈ Habrahabr | user “”},
(, . )
Referências:
, (hostsCount) – . . ? (: )
(, “”, {“”,“”,“”})
( ( ) [ ; “ ”], – n‑ “ ”; , LLTR, )
Permutation of bitsets (“lexicographic” order) derivation (mathematical induction)
( , __ [ , , , ]):
n=4; k=2 bitset i 0011 <- 0 0101 <- 1 1001 <- 2 0110 <- 3 1010 <- 4 1100 <- 5
Note: , .. bitset k i < bitset k i+1 , i – “ ”; k – ; n – .
“” ( ; /; , “”/), ?
- ( “B9”) ( “ ” O_o; , )
- “
_tmain() ” ( ) - , , – “
med() ” “ demed() ”
, :
:
“ ” (“ ”; “Permutations of multisets”).
Qual a diferença? ( [abcdef]), ( [000011]).
, ( ):
a => 0 b => 0 c => 0 d => 0 e => 1 f => 1
, , .. , , [abcdfe] ⇒ [000011], [000011] . (, )
{{000011}}.
{abcdef} 6! ( nuclphys.sinp.msu.ru/mathan/p1/m0204.html ).
.
, , ( [000011]) , ( (“1”) 2! × (“0”) 4! ) = 2! × 4! = 2! × (6−2)! .
= 6! ∕ (2! × (6−2)!).
( nuclphys.sinp.msu.ru/mathan/p1/m0204.html ), ( ru.wikipedia.org/wiki/?stable=1 ) – . . “ ” ( ru.wikipedia.org/wiki/?stable=1 ), “” “1” “0” – ( ru.wikipedia.org/wiki/?stable=1#___ ).
EN: → → combination: ( k‑combination with repetitions / k‑multicombination / multisubset ), ( en.wikipedia.org/wiki/Combination?stable=1#Example_of_counting_multisubsets ), “Stars and Bars” ( en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)?stable=1#Proofs_via_the_method_of_stars_and_bars ). (/ ): “1” – Star, “0” – Bar.
, “Stars and Bars” “” ( “ ” – k‑combination with repetitions) “ ” (permutations of multisets): en.wikipedia.org/wiki/Permutation?stable=1#Permutations_of_multisets .
RU: ru.wikipedia.org/wiki/?stable=1#__
PS stackoverflow.com/a/24257996 , ( – : n!∕((n−k)!); n⩵k; (n−k)!⇒1; n! ).
PPS [ alisey Trif ] ‑ / ( “Permutations of multisets”), ?
5: OMNeT++ 2
LLTR 5: OMNeT++ 2
( LLTR-Process sequence, – { “LLTD-Process (vFinal)”}, – , i → dstId, )
Referências:
6+7: +
LLTR 6:
, Golang.
Referências:
LLTR 7: (: “ ” – )
( 4 { //Wi‑Fi}, 3 ? – 2 ! – MacBook, Wi‑Fi Ethernet Thunderbolt)
( , “ ”, , “ ”)
( Wi‑Fi UDP broadcast – WNIC //. : How to override wifi broadcast speed limit? , Why does my UDP Broadcast wireless communication is capped at 1MBs? . 3 Mbps, 5 Mbps { }. MacBook {Wi‑Fi } Super‑, broadcast‑, unicast, {Wi‑Fi- ‑} unicast‑ broadcast { – Wi‑Fi}. , Wi‑Fi- – CPU . ‑.)
( UDP‑, !? : Windows “” {Windows NIC ?..}, API, “ CPU” { Win8 API, … (. “LLTD/flood/main.go”)}. “ ”. – API , “” . *nix { API}, , “” {. “LLTD/flood/main.go”}. : “ iperf3 and microbursts ”)
( → . { ; SMB}: → → → MacBook . , .)
( “LLTD/Prepare test environment.txt”)
Referências:
( “LLTD/Client.go”, “‑” – “LLTD/flood/main.go”)
( {Client1} NIC , – , , “ ” : “ interface always dead”)
Note: – Wi‑Fi ( ADSL‑/, ADSL – )
Note: ‑ : “” 100 Mbps unicast ; 100 Mbps broadcast . ( , /, )
TODO : : ( – ; ; +1/−1 ). Google Wave, Google Docs, Discus. :
- –
- – ,
- :
- , (.. ) – “” “ ” – (.. “” )
UserJS/UserCSS, , , .. , .
– – , UI (, , ) ( , “”). “” UserCSS. , , , ( ), ( ) ( ).
( ) ( ). ( UserJS UserCSS; Opera Presto , Firefox )
– “ OMNeT++ 2”.
TODO [x]: () + , + , , OMNeT++ v5.0b1 INET v3.0.0 + , ( ), – /
:
- OMNetProjectLLTD lltdapp + sim – LLTR , “LLTD” (“R” – “D”, //) [ “ 1”, .. article_1 a1_v0.30.0 ] { , }
- OMNetProject (before v0.9) lltdapp – (“LLTDClient.cc”: , DISCARD‑ “” ARP) [ article_1 ] { “for diff (LLTR)” – (diff) , , }
- OMNetProject (v0.9) lltdapp – (“LLTDClient.cc”: “
trafCount[stepN]++ ”): (. “ timeCalcEnd ” “ timeoutCalc ”), (“stat.txt”: ) [ 3] { “ , ”, .. , } - Timers (QPC) – – ( “Timers.cpp”; “ The Windows Timestamp Project: Adjustment of System Time (NTP) ”) [ 6] { , Golang, “ 6”}
- OMNetProject (v0.9.1) lltdapp – , : (“LLTDClient.cc”: “
sntpTimeOffset ” “ sntpLatency ” – , ) [ 3] - “fixed event time” – :
- OMNetProject (v0.9.3) lltdapp – v0.9.1 + , + v0.9.2ft [ 3]
- Get sequence (math induction) – : unicast_src_host i+1 = unicast_dst_host i , .. , (unicast dst), , (unicast src) [ 4] { , “” ( ) – “” , : “ ” ( ), , , }
- OMNetProject (v0.9.4) lltdapp – : , “ ” [ 5]
- OMNetProject (vFinal) lltdapp – [ 5]
- LLTD-Process (vFinal) – [ 5]
- GoLLTD – Go (“LLTD/old/main.old.go”) + + (“LLTD/Prepare test environment.txt”) + , : “Timers/”, “SNTP/”, “LLTD/flood/broadcast.txt”, “LLTD/Prepare test environment.txt”, “LLTD/flood/old/main.go”, “LLTD/flood/main.go”, “LLTD/” [ 6,7]
( ) (), . “ ” – , .
Note : – , ( ) – .
“ ”, , “ ”.
“ ”, , :
– . , – “ ”.
Note : “” – ( −1 ) ( ) (: ; ; – ); “‑‑‑” – ( ) , , ( ), , { “” ( ) – , , “ ?”; + “ ' ', ”, : (cookie) view‑only}
Note : (‑)
# Check‑list (TODO's)
TODO, .
PNG{SVG} (SVG thumbnail PNG) :
- PNG:
- [ 778px, 756px] ‑ ( . )
- ‑ 7z (un[7z]me), ( – “ ”, ‑ , ‑ )
- [ Photoshop] “Save for Web” → PNG 24+alpha
- [ GIMP] “8bpc RGBA” ( ), “ Save for Web ”
- 256 + alpha‑
- [ Adobe Fireworks] (Ctrl+Shift+X) → PNG‑8 + alpha
- []
- “” , Image Catalyst ( “” 2 : 2.1 2.5 , ):
- “” Image Catalyst 2.1 ([5] Xtreme profile)
Tools\config.ini
[options] ; , "true" "false". fs = true ; PNG. 0, %NUMBER_OF_PROCESSORS%. threatpng = 0 ; . , "true" "false". up = false [JPEG] ; Metadata. Metadata JPEG, "true" "false" , . dc = true ;Delete comment field (as left by progs like Photoshop & Compupic). de = true ;Strip Exif section (smaller JPEG file, but lose digicam info). di = true ;Delete IPTC section (from Photoshop, or Picasa). dx = true ;Deletex XMP section. du = true ;Delete non image sections except for Exif and comment sections. [PNG] ; ColorType BitDepth. ColorType BitDepth PNG, "true" "false". nc = true ; -. "Dirty Transparency" PNG c -, "true" "false". na = true ; Chunks. ; Chunks Chunks, "remove" Chunks Chunks, . ; Chunks Chunks, "keep" Chunks Chunks, . ; Chunks: ;text = iTXt,tEXt,zTXt ;color = cHRM,sRGB,iCCP,gAMA ;misc = bKGD,pHYs,sBIT,sPLT,hIST,tIME ;all = all of noncritical chunks hunks = remove all
Note : “ Image Catalyst 2.1 . Enter. ”, , , ( “Image Catalyst 2.1” “Image-Catalyst-2.1”)
- “” Image Catalyst 2.5 ([1] Xtreme profile)
Tools\config.ini
[options] ;Number of streams. If value early 0, is used value of parameter %NUMBER_OF_PROCESSORS%. thread=0 ;Automatic replacement of original images by the optimized. outdir=true ;Check update update=false [PNG] ;Parameters of optimization of PNG: ;/a# - PNG dirty transparency 0=Clean, 1=Optimize; ;/g# - PNG gamma 0=Remove, 1=Apply & Remove, 2=Keep; ;/na - PNG don't change RGB values for fully transparent pixels; ;/nc - PNG don't change ColorType and BitDepth; ;/np - PNG don't change Palette. xtreme=/a1 /g0 advanced=/a0 /g0 ;Remove PNG Metadata (Chunks). chunks=true [JPEG] ;Remove JPEG Metadata. metadata=true [GIF] ;Remove GIF Metadata. giftags=true
Note : “ Attention: running 2 of Image Catalyst. ”, , , ( “iCatalyst-2.5”)
merge_min.bat
@echo off setlocal enabledelayedexpansion :: Copy file from source to destination directory only if :: source file is smaller in size than in destination directory echo Src dir: %~f1 echo Dst dir: %~f2 echo --- for /r "%~1" %%A in (*) do ( set FileA=%%~fA set FileB=!FileA:%~f1=%~f2! set FileASize=%%~zA for %%Z in ("!FileB!") do set FileBSize=%%~zZ if !FileASize! LSS !FileBSize! copy "!FileA!" "!FileB!" )
- “.svg” ( ) – (SVG) (un[7z]me)
- SVG:
- {SVG 1.1; UTF-8; ; : ; : “1:100”; } ( , 2 – 1‑ )
- transform SVG ( 90 ) ( SVG ):
- DevTools transform ( “
[transform] ”) - “
Rotate90AndSwapWH() ” ( “ ”)
Rotate90AndSwapWH()
Sub Rotate90AndSwapWH() Dim sr As ShapeRange, s As Shape, w#, h# Set sr = ActiveSelectionRange On Error Resume Next boostStart2 "Rotate 90 and Swap WH" For Each s In sr s.GetSize w, h s.Rotate -90 s.SetSizeEx s.CenterX, s.CenterY, w, h Next s boostFinish2 End Sub
+ boostStart2/boostFinish2:
:
Private Sub boostStart2(ByVal unDo$) On Error Resume Next ActiveDocument.BeginCommandGroup unDo Optimization = True EventsEnabled = False End Sub Private Sub boostFinish2() On Error Resume Next EventsEnabled = True Optimization = False ActiveWindow.Refresh ActiveDocument.EndCommandGroup
- :
- ( )
- XML ( )
- ( ):
- “
DOCTYPE ” “ Creator ” “ 96ppi ” ( ppi CorelDRAW SVG) - “
metadata ”, “ id ” ( ) - svg:
- “
xmlns ” “ xml:space ” - “
xmlns:xlink ” - [, “
style ” “ fill-rule:evenodd; clip-rule:evenodd ”] “ version ” “ style ” ` style="margin:16px auto" shape-rendering="geometricPrecision" fill-rule="evenodd" clip-rule="evenodd" xmlns="http://www.w3.org/2000/svg" version="1.1" baseProfile="full" `
- ( ) `
" ` ` " `
- ( <rect> <g>), , “
viewBox ” ( <svg>)- , SVG , CorelDRAW – , , , ( , )
- SVG optimiser :
- :
- Whitespace: pretty
- Style type: optimal
- Truncate * numbers: unchanged
- ( , “Remove clean group”, )
- <svg>
- <style> – SVG optimiser CDATA ( )
- XML
- PNG SVG:
- “PNG_SVG.bat” ( 7-Zip SVG: “
-txz -m0=LZMA2:lc1:pb0 -mx ”)
PNG_SVG.bat
@echo off setlocal enabledelayedexpansion :: PNG+7Zip{SVG} echo PNG dir: %~f1 echo SVG dir: %~f2 echo --- for /r "%~2" %%A in (*.svg) do ( set SVG=%%~fA set PNG=!SVG:%~f2=%~f1!.png "%ProgramFiles%\7-Zip\7z.exe" a dummy -txz -m0=LZMA2:d96m:fb74:lc1:pb0 -mx -so -- "!SVG!" >> "!PNG!" )
“ LZMA2:d96m:fb74:lc1:pb0 ”?
‑ ( “RingSync_no_problem.svg”):
- "LZMA2:d96m:fb64" 6804 byte - "LZMA2:d96m:fb74" 6800 byte - "LZMA2:d96m:fb74:lc2" 6812 byte - "LZMA2:d96m:fb57:lc2" 6780 byte - "LZMA2:d96m:fb57:lc1" 6768 byte - "LZMA2:d96m:fb56:lc1" 6760 byte - "LZMA2:d96m:fb49:lc1" 6760 byte - "LZMA2:d96m:fb56:lc1:pb0" 6696 byte - "LZMA2:d96m:fb46:lc1:pb0" 6688 byte (fb44-fb47) - "LZMA2:d96m:fb63:lc1:pb0" 6688 byte - "LZMA2:d96m:fb66:lc1:pb0" 6684 byte - "LZMA2:d96m:fb74:lc1:pb0" 6692 byte
svg “ LZMA2:d96m ” (fb64), “ LZMA2:d96m:fb74:lc1:pb0 ” .
Note : Image Catalyst: ping timeout, ( 2.5) ( 2.1 – )
Image Catalyst.bat
v2.1 diff:
182c182 < if defined thrt >nul 2>&1 ping -n 1 -w 500 127.255.255.255 & goto:waithreat --- > if defined thrt >nul 2>&1 timeout /t 1 /nobreak & goto:waithreat 203c203 < 1>nul 2>&1 ping -n 1 -w 500 127.255.255.255 --- > 1>nul 2>&1 timeout /t 1 /nobreak 237c237 < if exist "%~1" (1>nul 2>&1 ping -n 1 -w 500 127.255.255.255 & goto:waitflag) --- > if exist "%~1" (1>nul 2>&1 timeout /t 1 /nobreak & goto:waitflag) 513c513 < if exist "%tmppath%\typelog.lck" (1>nul 2>&1 ping -n 1 -w 500 127.255.255.255 & goto:savelog) --- > if exist "%tmppath%\typelog.lck" (1>nul 2>&1 timeout /t 1 /nobreak & goto:savelog) 534c534 < if "%jpeg%" equ "0" if "%png%" equ "0" 1>nul ping -n 1 -w 500 127.255.255.255 2>nul & goto:finmessage --- > if "%jpeg%" equ "0" if "%png%" equ "0" 1>nul timeout /t 1 /nobreak 2>nul & goto:finmessage 572c572 < 1>nul ping -n 1 -w 500 127.255.255.255 2>nul --- > 1>nul timeout /t 1 /nobreak 2>nul
V2.5 diff:
319,320c319 < call:division float 1024 100 < call:echostd " In - !float! " --- > call:echostd " In - !float! " 322d320 < call:division change 1024 100 324,325c322 < call:division float 1024 100 < call:echostd " Out - !float! (!change! , %5%%%%%%)" --- > call:echostd " Out - !float! (!change! , %5%%%%%%)" 362,363c359,360 < set /a "ww=%random%%%%1" < 1>nul 2>&1 ping -n 1 -w %ww% 127.255.255.255 --- > set /a "ww=%random%%%%1/1000" > 1>nul 2>&1 timeout /t %ww% /nobreak 707c704 < if %jpeg% equ 0 if %png% equ 0 if %gif% equ 0 1>nul 2>&1 ping -n 1 -w 500 127.255.255.255 & goto:finmessage --- > if %jpeg% equ 0 if %png% equ 0 if %gif% equ 0 1>nul 2>&1 timeout /t 1 /nobreak & goto:finmessage 741d737 < call:division changePNG 1024 100 747d742 < call:division changeJPG 1024 100 753d747 < call:division changeGIF 1024 100 800c794 < call:echostd " Total %1: %%change%1%% , %%perc%1%%%%%%" --- > call:echostd " Total %1: %%change%1%% , %%perc%1%%%%%%"
Note : Image Catalyst ( ) CP866, diff, , .
:
- 778px – (780px – − 2px )
- 756px – (758px – − 2px )
- 738px – (740px – − 2px )
- Image Catalyst v2.1 v2.5, ( “ merge_min.bat ”).
- – : habrastorage “dwbmwbyvlzes80cep1hvcdb5iy.png” () HTTP‑ “
Content-Disposition : inline ;... ”, , , (): “dwbmwbyvlzes80cep1hvcdb5iy.png#real-name.png”. , – ( ). SVG – (), , … - (id, name). . ( – , , – )
- , ( ).
- ‑ (un[7z]me), habrastorage – , CloudFlare Polish .
Note : habrastorage SVG ( ): ( ), PNG{SVG} ( SVG, , – ) ( , , / – ‑ / , )
git:
Note : habrahabr <oembed> , GitHub , .
Note : TODO‑ , 43 KiB ( “ 0”), 69 KiB ( “ 1”), 45 KiB ( ).
