Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Алгоритмдік саудада аз уақыт үшін көбірек орын
Algorithm trading more space for lower time
Компьютер ғылымында кеңістік-уақыт саудасы, сондай-ақ уақыт-жад саудасы немесе алгоритмдік кеңістік-уақыт континуумы деп те аталады, бұл алгоритмнің немесе бағдарламаның көбірек орынды пайдалану арқылы уақытты қысқартуына мүмкіндік беретін жағдай. Мұндағы "орын" дегені берілген міндетті орындау үшін қажетті деректерді сақтау көлемі (RAM, HDD және т.б.), ал "уақыт" – міндетті орындауға жұмсалатын уақыт (есептеу уақыты немесе жауап беру уақыты). Белгілі бір кеңістік-уақыт саудасының тиімділігіне CPU жылдамдығы, жад көлемі сияқты тұрақты және өзгермелі шығындар әсер етеді және оның пайдасы азая береді.
A space–time trade off, also known as time–memory trade off or the algorithmic space time continuum in computer science is a case where an algorithm or program trades increased space usage with decreased time. Here, space refers to the data storage consumed in performing a given task (RAM, HDD, etc. ), and time refers to the time consumed in performing a given task (computation time or response time). The utility of a given space–time tradeoff is affected by related fixed and variable costs (of, e. g., CPU speed, storage space), and is subject to diminishing returns.
Тарих
Уақыт-жад айырбасының биологиялық қолданылуы жануарлар мінез-құлқының бастапқы кезеңдерінде көрінеді. ДНҚ-да сақталған білімді немесе стимулдарға реакцияны "инстинкт" ретінде кодтау, уақыт өте маңызды жағдайларда "есептеу" қажеттілігін жояды. Компьютерлерде іздеу кестелері ең алғашқы операциялық жүйелерден бері қолданылып келеді. 1980 жылы Мартин Хеллман криптоанализ үшін уақыт-жад айырбасын пайдалануды алғаш ұсынды.
Biological usage of time–memory tradeoffs can be seen in the earlier stages of animal behavior. Using stored knowledge or encoding stimuli reactions as "instincts" in the DNA avoids the need for "calculation" in time critical situations. More specific to computers, look up tables have been implemented since the very earliest operating systems. In 1980 Martin Hellman first proposed using a time–memory tradeoff for cryptanalysis.
Іздеу кестелері мен қайта есептеу
Кездесетін жағдай – іздеу кестесін пайдаланатын алгоритм: оның іске асылуында кесте толығымен болуы мүмкін, бұл есептеу уақытын қысқартады, бірақ қажетті жад мөлшерін арттырады, немесе кестедегі жазбалар қажет болғанда есептелінеді, бұл есептеу уақытын ұзартуы мүмкін, бірақ жадқа қойылатын талаптарды азайтады.
A common situation is an algorithm involving a lookup table: an implementation can include the entire table, which reduces computing time, but increases the amount of memory needed, or it can compute table entries as needed, increasing computing time, but reducing memory requirements.
Деректер қорының индекстері мен кесте сканерлері
Деректер қорын басқару жүйелері деректер қорының индексі дерек құрылымдарын жасау мүмкіндігін ұсынады. Индекстер қосымша орынды пайдалана отырып, іздеу операцияларының жылдамдығын арттырады. Индекстер болмаған жағдайда, қажетті деректерді табу үшін кейде толық кесте шарлау операцияларын орындау қажет болады.
Database Management Systems offer the capability to create Database index data structures. Indexes improve the speed of lookup operations at the cost of additional space. Without indexes, time consuming Full table scan operations are sometimes required to locate desired data.
Сығымдалған және сығымдалмаған деректер
Деректерді сақтау мәселесіне кеңістік-уақыт арасалмағын қолдануға болады. Деректер сығылмай сақталса, көбірек орын керек болады, бірақ сығылған деректерге қарағанда қол жеткізу уақыты аз болады (сығылған деректер орынды азайтады, бірақ сығылымды ашу алгоритмін іске қосуға уақыт қажет). Нақты мәселеге байланысты, екі тәсіл де қолданылуы мүмкін. Сонымен қатар, сығылған деректермен тікелей жұмыс істеуге болатын сирек жағдайлар бар, мысалы, сығылған биттік карта индекстерінде, сығылған күйде жұмыс істеу сығылмаған күйден гөрі жылдам болады.
A space–time trade off can be applied to the problem of data storage. If data is stored uncompressed, it takes more space but access takes less time than if the data were stored compressed (since compressing the data reduces the amount of space it takes, but it takes time to run the decompression algorithm). Depending on the particular instance of the problem, either way is practical. There are also rare instances where it is possible to directly work with compressed data, such as in the case of compressed bitmap indices, where it is faster to work with compression than without compression.
Қайта рендеринг пен сақталған суреттер
Векторлық кескіннің SVG көзін ғана сақтау және оны әрбір бет сұралымында растрлік кескін ретінде көрсету – уақытты кеңістікке сату болар еді; уақыт көбірек жұмсалады, бірақ орын аз болады. Ал бет өзгерген кезде кескінды көрсетіп, көрсетілген кескіндерді сақтау – кеңістікті уақытқа сату; орын көбірек жұмсалады, бірақ уақыт аз болады. Бұл техника жалпы алғанда кэштеу деп аталады.
Storing only the SVG source of a vector image and rendering it as a bitmap image every time the page is requested would be trading time for space; more time used, but less space. Rendering the image when the page is changed and storing the rendered images would be trading space for time; more space used, but less time. This technique is more generally known as caching.
Кіші код пен циклді ашу
Циклды ашу арқалы үлкен код көлемі жоғары бағдарлама жылдамдығымен алмастырылуы мүмкін. Бұл техника циклдың әрбір итерациясы үшін кодты ұзартады, бірақ әр итерацияның соңында цикл басына қайта оралуға кеткен есептеу уақытын қысқартады.
Larger code size can be traded for higher program speed when applying loop unrolling. This technique makes the code longer for each iteration of a loop, but saves the computation time required for jumping back to the beginning of the loop at the end of each iteration.