Jak napsat objekt N to N

[CPU]

Ahoj,

potřebuji napsat objekt, který se bude chovat takhle:

Mějme 2D pole objektů:
Řekněme matice 3x3 pro jednoduchost, ve skutečnosti pole 65 535 * 65 535.

A1__B1__C1
A2__B2__C2
A3__B3__C3

Objekt A může posílat jen do B, B může posílat jen do C.
Objekt A nemůže posílat do jiného A, B do jiného B, C do jiného C.
Data jdou z vrstvy do vrstvy, nikdy jinak.

Objekt B1 dostal hodnotu 50 od objektu A1, to si zapamatuje.
Objekt B1 dostal hodnotu 50 od objektu A2, = OK.
Objekt B1 dostal hodnotu 60 od objektu A3, a pokud přijdou data z A3, musím to vědět pro příště.

98% hodnot je stejných, ale bohužel se občas stane, že některá hodnota stejná není.
Objekt si musí pamatovat, co od kterého objektu dostal, bohužel v plné cestě.

Pro matici 3*3 to je snadné.
Ale pro 65 535 * 65 535 prvků si pamatovat vždy celou cestu je problém.
(Rozdíl může nastat v jakémkoliv prvku po cestě.)

Jak by takový objekt mohl vypadat, aby se pamatovala celá cesta? A přitom aby ty objekty nebyly ohromné. Resp. jak k tomu chytře přistoupit?

[Reklama]

[Filip Jirsák]

Jaký je poměr mezi cestami, které reálně nastanou, a všemi možnými cestami? Jestli je potřeba si pamatovat celou matici, nebo se vyplatí pamatovat si jen ty cesty, které maticí reálně prošly? Objekt si má pamatovat jen nejvyšší hodnotu, která se k němu dostala, a kterými uzly hodnota prošla v předchozích vrstvách? Podle čeho se určuje, kterému objektu další vrstvy se hodnota pošle?

[CPU]

Jeden vstup (na začátku) je mapovaný na jeden výstup (na konci, až to probublá nakonec).
Tj. vstupní hodnota 100 se změní třeba na 106 v průběhu celého zpracování (průchod skrz 65535 vrstev).
100>22>99....
Potřebuji získat výstup pro všechny vstupní hodnoty, tj. vždy to musí probublat až nakonec.

V 99% případů buňka C1 přičte 50.
V 1% buňka C1 přičte 60, protože data přišla z A2 skrz B3...

Jak nad tím přemýšlím, tak si říkám, jestli bych pro každý objekt neměl evidovat:
A/N, pokud existuje výjimka
A pak vést seznam výjimek někde bokem.

Tím bych ušetřil pamět.
A je možné, že počet objektů, kde dochází k výjimkám, je nějak ohraničený nebo někam seskupený.

Já vlastně nevím, kolik těch výjimek je, protože aktuálně se to řeší dotazem databázově, kdy zprocesování téhle tabulky trvá sekundy a v případě výjimky se spustí skript, který hodnotu spočítá ručně, což zabere třeba minutu.

Pak bych to rozložil na 2D pole objektů 65535 x 65535 a výjimky neskladoval uvnitř.
Znamenalo by to pro každou vrstvu udělat lookup table, kde by se to evidovalo.

Jde mi i o to, abych celou tu opičárnu nemusel 10x přepisovat, než zjistím, že to nevyřeším 

[Tomáš Procházka]

A přesně proto programátoři nepřijdou o práci díky AI. Protože ani programátoři samotní neumí popsat zadání v lidské řeči.

[xyz]

Zkus nejdriv definovat problem. 
Cili: 1) Co jsou vstupy
       2) Co jsou vystupy
       3) Jakym zpusobem se ze vstupu spocita vystup

Pote nekolik prikladu vstup + vystup

A az bude jasne, co se vlastne ma resit za problem, tak pak se vymysli datova struktura.

[Reklama]

[snugar_i]

To zní jako hodně divná neuronka...

Opravdu máš reálně 65535^2 (=4 miliardy) objektů, kde každý má seznam pravidel?

[peete]

To mi vazne pripomina ty zmatene zakazniky, se kterymi kazda schuzka je vlastne neustale vysvetlovani co to ma vlastne delat a proc. Ti stejni maji v oblibe posilani internich materialu a nesmyslnych xls souboru. Ja mam teda radsi zakazniky, kteri to dokazou velmi dobre formulovat hned na zacatku a srozumitelne pro druhe.

[Filip Jirsák]

První věc, co potřebujete zjistit pro návrh efektivní datové struktury pro tenhle případ, je zjistit, kolik existuje těch výjimek. Protože pokud jich je relativně málo, stačí evidovat jen ty výjimky (pravděpodobně ve stromu), a když nebude pro daný vstup existovat výjimka, nepotřebujete předpokládám ukládat nic (na výstupu je to samé, co na vstupu).

No a že by těch výjimek existovalo opravdu hodně, aby se hodilo řešit jinou datovou strukturu, o tom silně pochybuju – i vzhledem k popisu, jak se to zpracovává teď. To nevypadá jako popis něčeho, kde by těch výjimek byly miliony.

[CPU]

To zní jako hodně divná neuronka...

Protože to není neuronka.
Dnes každý ve 2D poli vidí neuronku...ale tohle není ani strojové učení.

Opravdu máš reálně 65535^2 (=4 miliardy) objektů, kde každý má seznam pravidel?

Ano, ale dá se s tím snadno pracovat, protože při zpracování je možné dělat řezy,  protoze každý prvek komunikuje jen s jedním prvkem v následující vrstvě.

Klidně bych mohl mít 65535 počítačů...(samozřejmě nemohl, bylo by to nepraktické).

Ale mohu zpracovat pár miliard objektů ve vrstvách 0..128, pak načíst z SSD další vrstvy ... a pak znova a znova.

[CPU]

První věc, ..., je zjistit, kolik existuje těch výjimek.

Ano, máš pravdu, poprvé to musím napsat tak, abych si dokázal posbírat to, co potřebuji.

[speculatius]

To znie ako pokus naprogramovať neurónovú sieť. Ak je to tak, odporúčam túto sériu kurzov https://www.coursera.org/specializations/deep-learning. V prvom kurze sa prejde všetko od základov algebry až po sprogramovanie kompletnej samoučiacej siete.

Ak je to inak, zadanie vyvoláva fúru otázok. Ako presne mám rozumieť "plnej ceste". Výpočet beží v nejakých lock-step iteráciách, zľava doprava, alebo ad-hoc? Ako sa z N prijatých čísel vygeneruje jedno, ktoré sa pošle ďalej?... Naozaj by to chcelo popísať problém konkrétnejšie.

[Tomáš Crhonek]

Opravdu máš reálně 65535^2 (=4 miliardy) objektů, kde každý má seznam pravidel?

Což je dost málo. 4mld*64b = 4GB informací + pravidla, pohodlně se to vejde třeba do 256GB RAM, což lze mít i v desktopu na Threadripperu.

[RDa]

By te bolelo napsat co ta skolni uloha ma presne delat v cestine?

Proste popis algoritmu a vynech implementacni detaily jako objekt,matice,hodnota,cesta(wtf to je?).

V tom popisu ktery se tady objevil se nejsem schopen zorientovat.

[František Ryšánek]

Ahoj,

potřebuji napsat objekt, který se bude chovat takhle:

Mějme 2D pole objektů:
Řekněme matice 3x3 pro jednoduchost, ve skutečnosti pole 65 535 * 65 535.

A1__B1__C1
A2__B2__C2
A3__B3__C3

Objekt A může posílat jen do B, B může posílat jen do C.
Objekt A nemůže posílat do jiného A, B do jiného B, C do jiného C.
Data jdou z vrstvy do vrstvy, nikdy jinak.
...

Spíš na okraj: v jakém jazyce to chcete psát? V jakém umíte?

Obecně:

Máte-li "matici" nějakých prvků, a potřebujete držet data o každém z nich, nebo o většině z nich, může být základem "2D pole o statických rozměrech" = alokovat jedním vrzem úplné pole objektů.
Sáhnout na objekt na konkrétních souřadnicích v matici pak víceméně znamená, vynásobit číslo sloupce délkou sloupce, připočíst adresu ve sloupci, to celé třeba ještě vynásobit alokační velikostí pointeru (64b systém = 8 bajtů) a připočíst bázovou adresu celého pole. Je to poměrně jednoduchá adresní aritmetika s pevným počtem kroků na tuto operaci.

Pokud ve skutečnosti potřebujete držet data jenom o nějaké podmnožině té "matice", tzn. matice je "řídká", dává smysl kvůli úspoře RAM (popř. také místa na disku) postavit tu matici pomocí "dynamických datových struktur" z prvků jako je pointer, seznam, seznam pointerů, kombinovaná obousměrná uspořádání typu "A ukazuje na právě jeden B, ale B potřebuje držet seznam pointerů na několik A", setříděný seznam, key->value asociativní pole, strom, partial mesh s jednosměrnými nebo obousměrnými vazbami...

Třeba řídké pole X*Y by se dalo postavit jako asociativní pole vnořené do asociativního pole, a konečným prvkem by mohly být objekty (held by value) nebo pointery/reference na ně...
Nebo dva vnořené spojové seznamy :-)
Spojový seznam má tu potenciální nevýhodu, že je třeba ho procházet stylem "předchozí/následující" (sledovat pointery). Takže operace "nalézt prvek číslo 2307" je otrava. Operaci vyhledání mají naopak rychlou asociativní kontejnery (indexy) založené na binárních stromech nebo hash tabulkách.

Můžeme mluvit o pointerech v low-level smyslu = adresa v paměťovém prostoru procesoru. Vzhledem k rozměru dat a vzhledem k letopočtu ty adresy budou 64bitové. Každý pointer uložený v paměti zabere 64 bitů = 8 bajtů.

Nebo vzhledem k tomu, že máte tabulku těsně pod 4 Giga objektů, můžete se odkazovat na pořadové číslo objektu, které bude 32bitové, nebo na dvě souřadnice každou 16b, nebo pokud víte, že odkazy jsou vždy zásadně do dalšího sloupce, tak vlastně stačí "svislá souřadnice" = 16b číslo (a který sloupec je následující může být dáno implicitně)...

Mimochodem pokud tu matici uděláte 65536 x 65536, můžete v části adresní aritmetiky pro rozklad na řádek/sloupec používat operace maskování a posuvu (bit-banging) namísto násobení a dělení... tedy pokud pro takovou operaci najdete ve svých algoritmech uplatnění...

Vlastně jsem ale mířil k ponaučení, že i "dynamické datové struktury" mají svou režii, a tedy se vyplatí až od určité "míry prořídnutí matice".

Jestli jsem trochu pochopil zadání, možná budete potřebovat nějaký hybridní přístup: pole o pevných rozměrech [X;Y] a možná nikoli řídké, kde v každé "buňce" bude nějaký "objekt" (C struct, C++ instance třídy apod.) který bude držet hrst proměnných, odkazů a může z něj rašit nějaký dynamický seznam nebo stromek apod.

A dále jak psal @speculatius... pokud algoritmus běží mezi dvěma-třemi řádky po sobě jdoucími, a nemáte dost RAM na celou datovou sadu, možná by se dal úplný soubor dat držet na disku a natáhnout do RAM vždycky jenom nějakou "podmnožinu", potřebnou ke zpracování... (několik sloupců po sobě jdoucích)

Ta data natékají do matice kontinuálně / iterativně do levého sloupce, a postupně probublávají doprava?
A je to tak, že dodáte vstup do levého sloupce, pak se spočítá celá matice, zahodí se mezivýsledky a všechno znova?

A říkáte, že v každé buňce potřebujete kompletní cestu přes všechny předchozí sloupce?
Podle "algoritmu agregace" se může jednat o seznam (délka = číslo sloupce), nebo strom (hloubka = číslo sloupce).
V každé "iteraci zpracování" se "dosavadní cesta" v aktuální buňce matice odhákne, a "předá se příslušné buňce o sloupec vpravo, ke vhodnému zaagregování do výsledné cesty pro tuto iteraci" (seznam/strom o patro naroste).
Mimochodem taková úplná "cesta" bude žrát dost paměti i pokud se bude jednat o prostou sekvenci (seznam), nedejbože strom. Předpokládám, že si v tomto bodě vysvětluji zadání špatně, protože to začíná připomínat ten vtipný čínský příběh se šachovnicí a zrnky rýže...

Potřebujete tu cestu uchovávat během výpočtu pro všechna políčka v tabulce, nebo jenom pro políčka v aktuálně počítaném sloupci?

Potřebujete během výpočtu uchovávat (alokovat) základní hodnoty pro celou matici, nebo vlastně stačí jenom pro aktuální sloupec? (nebo dva nebo tři)

Poslední dva dotazy míří na paměťovou náročnost.

[ondrah]

A zamyslel ses důkladně, jestli ten prvotní úkol, kvůli kterému tohle celé lepíš, nejde vyřešit i jinak než s pomocí nějaké přebujelé datové struktury?