it-swarm-eu.dev

Co jsou invarianti, jak je lze použít a už jste to někdy použili ve svém programu?

Čtu Coders at Work a v něm se hodně mluví o invariantech. Pokud jsem to pochopil, invariant je stav, který platí před i po výrazu. Jsou mimo jiné užitečné při dokazování správnosti smyčky, pokud si správně pamatuji svůj kurz Logic.

Je můj popis správný nebo mi něco uniklo? Už jste je někdy použili ve svém programu? A pokud ano, jak z toho měli prospěch?

54
gablin

V OOP je invariant množina tvrzení, která musí vždy platit během života objektu, aby byl program platný. Mělo by to platit od konce konstruktoru do začátku destruktoru, kdykoli objekt aktuálně neprovede metodu, která změní jeho stav.

Příkladem invariantu může být to, že přesně jedna ze dvou členských proměnných by měla být nulová. Nebo, že pokud jeden má danou hodnotu, pak sada povolených hodnot pro druhou je tato nebo ta ...

Někdy používám členskou funkci objektu k ověření, že invariant má. Pokud tomu tak není, uplatní se tvrzení. Metoda se nazývá na začátku a na konci každé metody, která mění objekt (v C++ je to pouze jeden řádek ...)

47
Xavier Nodet

No, věci, které vidím v tomto vláknu, jsou skvělé, ale mám definici „invariantu“, který mi v práci nesmírně pomohl.

Invazivní je jakékoli logické pravidlo, které musí být dodrženo během provádění vašeho programu a které může být sděleno člověku, ale ne vašemu kompilátoru.

Tato definice je užitečná, protože rozděluje podmínky do dvou skupin: těm, které kompilátoru mohou důvěřovat, a těm, které musí být dokumentovány, diskutovány, komentovány nebo jinak sděleny přispěvatelům, aby mohli interagovat s kódovou základnou bez zavádění chyb .

Tato definice je také užitečná, protože umožňuje používat zobecnění „Invarianty jsou špatné“.

Jako příklad lze uvést, že řadič v automobilu s manuální převodovkou je zkonstruován tak, aby se vyhnul invariantu. Kdybych chtěl, mohl bych postavit převodovku s jednou pákou pro každý rychlostní stupeň. Tato páka může být dopředu („zapnutá“) nebo zpět („vypnutá“). V takovém systému jsem vytvořil „invariant“, který by mohl být jako takový dokumentován:

„Je důležité, aby byl aktuálně zařazený rychlostní stupeň vyřazen před zařazením jiného rychlostního stupně. Při současném zařazení jakýchkoli dvou rychlostních stupňů dojde k mechanickému namáhání, které roztrhne převodovku. Před zařazením dalšího vždy odpojte právě zařazený rychlostní stupeň.“

A tak, jeden by mohl obviňovat přerušené přenosy na nedbalé jízdě. Moderní auta však používají jedinou tyč, která se otáčí mezi rychlostními stupni. Je navržen tak, aby na moderním vozidle s řadicí pákou nebylo možné současně zařadit dva rychlostní stupně.

Tímto způsobem bychom mohli říci, že přenos byl navržen tak, aby „odstranil invariant“, protože to neumožňuje, aby byl mechanicky nakonfigurován způsobem, který porušuje logické pravidlo.

Každý invariant tohoto druhu, který odeberete ze svého kódu, je vylepšení, protože snižuje kognitivní zatížení práce s ním.

15
Daniel Burbank

Na základě následující nabídky od Coders At Work ...

Ale jakmile víte, že invariant je udržující, můžete vidět, ach, pokud budeme udržovat tento invariant, dostaneme čas na vyhledání protokolu.

... myslím, že "invariant" = "podmínka, kterou chcete udržet, abyste zajistili požadovaný efekt".

Zdá se, že invariant má dva smysly, které se jemně liší:

  1. Něco, co zůstane stejné.
  2. Něco, co se snažíte zachovat, abyste dosáhli cíle X (například „doba vyhledávání protokolu“ výše).

Takže 1 je jako tvrzení; 2 je jako nástroj k prokázání správnosti, výkonu nebo jiných vlastností - myslím. Viz článek z Wikipedie pro příklad 2 (prokazující správnost řešení MU puzzle).

Ve skutečnosti je třetí smysl pro invariant:

.3. Co má program (nebo modul nebo funkce) dělat; jinými slovy, jeho účel.

Ze stejného rozhovoru Coders At Work:

Ale díky čemu je spravovatelnost velkého softwaru možná, jsou některé globální invarianty nebo výroky o tom, co má dělat a jaké věci mají být pravdivé.

3
Jonathan Aquino

Invariant (v běžném slova smyslu) znamená některé podmínky, které musí být pravdivé v určitém okamžiku nebo dokonce vždy, když je program spuštěn. např. PreConditions a PostConditions lze použít k prosazení některých podmínek, které musí být pravdivé, když je funkce vyvolána a když se vrací. Invarianty objektů lze použít k tvrzení, že objekt musí mít platný stav po celou dobu, kdy existuje. Toto je princip konstrukce podle smlouvy.
Použil jsem invarianty neformálně pomocí kontrol v kódu. Ale v poslední době hraji s kódem smlouva knihovna pro .Net , která přímo podporuje invarianty.

3
softveda

Invariant je jako pravidlo nebo předpoklad, který lze použít k diktování logiky vašeho programu.

Předpokládejme například, že máte nějakou softwarovou aplikaci, která sleduje uživatelské účty. Předpokládejme také, že uživatel může mít více účtů, ale z jakéhokoli důvodu musíte rozlišovat mezi hlavním účtem uživatele a účtem „alias“.

Může se jednat o záznam DB nebo o něco jiného, ​​ale prozatím můžeme předpokládat, že každý uživatelský účet je reprezentován objektem třídy.

class userAccount {private char * pUserName; soukromý znak * pParentAccountUserName;

...}

Neměnný by mohl být předpoklad, že pokud pParentAccountUserName je NULL nebo prázdný, pak je tento objekt nadřazeným účtem. Tento invariant můžete použít k rozlišení různých typů účtů. Pravděpodobně existují lepší metody, jak rozlišit různé typy uživatelských účtů, takže mějte na paměti, že je to pouze příklad, jak ukázat, jak by mohl být invariant použit.

1
Pemdas

Pocházíme z fyzického pozadí, ve fyzice máme invarianty, což jsou v podstatě veličiny, které se nemění po celou dobu výpočtu/simulace. Například ve fyzice je pro uzavřený systém celková energie zachována. Nebo ve fyzice, pokud dojde ke srážce dvou částic, musí výsledné fragmenty obsahovat přesně energii, se kterou začaly, a přesně stejnou hybnost (vektorové množství). Obvykle není dostatek invariantů k úplnému určení výsledku. Například ve srážce dvou částí máme čtyři invarianty, tři složky hybnosti a složku energie, ale systém má šest stupňů volnosti (šest čísel popisuje jeho stav). Invarianty by měly být zachovány v rámci chyby zaokrouhlování, ale jejich zachování neprokáže, že řešení je správné.

Obvykle jsou tyto věci důležité jako kontroly rozumnosti, ale samy o sobě nemohou prokázat správnost.

1
Omega Centauri