Байт містить 256 символів?

Дуже перепрошую за тупе питання, але під час читання літератури трохи заплутався і хотів би поставити кілька запитань
1) У V,S типу даних byte присвоюється число від 0 до 255 тобто завдяки інструкції та двійковій системі 0,1,2,3,4. 255 вважається числом команд?
2) Я правильно розумію що в чистий байт (без інструкцій) можна впхнути скажемо 256 чисел? (Типо 1111111111111111. )

у воєнний час у байт можна всунути і більше

але зазвичай працює приблизно так

число одне значення його від 0 до 255

тобто завдяки інструкції та двійковій системі 0,1,2,3,4. 255 вважається числом команд

Ось тут не зрозумів, до чого тут команди? Якщо ви про машинні команди, то вони можуть бути більше одного байта.

Я правильно розумію що в чистий байт (без інструкцій) можна впхнути скажемо 256 чисел? (Типо 1111111111111111. )

Знову ж таки, до чого тут інструкції? А про байт, ви уточніть про яке байте мова, якщо про C#, то там тип даних byte має розмір 8 біт, отже може зберігати одне з 256 різних значень від 0 до 255. Якщо про байт, як про мінімально адресовану комірку пам'яті, то у більшості сучасних комп'ютерних систем 8 біт, але були раніше (може і зараз є) і не 8 https://ua.wikipedia.org/wiki/%D0%91%D0%B0%D0%B9%D1%82

Що це за команди? Байт це мінімальна кількість пам'яті з яким працює процесор, він може взяти 1, 2, 3 байти, але тільки цілими. Біти ви не впихає, байт так і залишиться байтом навіть якщо у вас менше 8 одиниць, просто спочатку будуть нулі, ні ким не використовуються. Тобто [0000] – 0, [0001] – 1, [0010] – 2, [0011] – 3 і т.д. просто комбінування і якщо ви приміром кладете в 111, а потім 11, то в пам'яті це буде: [00000111] [00000011].є способи тримати в одному байті кілька змінних, в основному бітові прапори або числа до 16 (дуже рідко, бо ліньки). Кількість значень це 2 (оскільки це двійкова система) у ступеня кількості БІТ, 1 байт = 8 біт отже 2^8=256. Можете собі взяти два - три об'єкти (irl) викласти в ряд, почати перевертати і подивитися скільки варіантів у вас вийшло.

Зберігаємо числа економно

Нещодавно в одному з проектів постало завдання: є набір множин (Set), які треба досить ефективно зберігати в оперативній пам'яті. Тому що множин багато, а пам'яті мало. І із цим треба щось робити.

Оскільки мова, якою все це написано — C#, тобто нюанси. А саме, що стандартний HashSet на зберігання одного числа витрачає 16 байт, також впливає філ фактор. Є більш ефективні реалізації (коли і про них напишу), але з іншого боку, можна ж тупо зберігати в масивах, по 4 байти на число (потрібно зберігати інти), що досить ефективно. Але чи можна ще зменшити?

Відразу скажу, у мене немає відповіді, як краще зробити, можливо, її не існує, бо є безліч факторів, пов'язаних з особливостями розподілу конкретних даних. Але є ідеї, якими поділюся: які варіанти економії пам'яті існують. Також рекомендую до прочитання посту подумати самостійно, таки це непогана розминка для розуму. Для певності сформулюю завдання так:

Є набір невід'ємних унікальних інтів (32 біти). Потрібно зберігати їх ефективно в оперативній пам'яті, з операцій створення набору та отримання всіх елементів. Не потрібно отримувати елементи індексу, додавати нові або видаляти.

У статті буде багато літер та цифр і жодної картинки (крім упакованого котика на КДПВ).

Я спеціально не вказую що за проект, що завдання конкретно, т.к. загалом, це не має значення. Допустимі рішення сильно залежать від даних. Які краще підходять для одних, які для інших, також не забуваємо про швидкість роботи. Десь краще максимально економити пам'ять, а десь варто дотримуватися балансу.

Також, не розглядаю рішення виду – тупо зберігати на диску та використовувати кеш для гарячих даних, це окреме завдання.

Просто розуміння кількості даних, із якими зіштовхнувся: кілька мільйонів сетів, у кожному з яких від одного елемента до двох мільйонів. У пам'яті це займає близько 10 ГБ

Отже, у нас є базові дані - масив з інтів, 4 байти (32 біти) на число. Відштовхуватимемося від цього показника.

Для початку висловлю геніальну думку: щоб число займало в пам'яті менше 32 біти, треба зберігати його, використовуючи меншу кількість бітів. Крута ідея, так? А люди за подібне набувають популярності та визнання. Тож чим я гірший.

Ліричний відступ: кілька років тому фахівці з РЗ з'ясували, що якщо робити колеса круглими та однакового розміру, то поїзд йде швидше та тихіше.

Розділяємо числа за розміром

Для початку просте рішення: Числа від 0 до 255 можна зберігати за допомогою 1 байта на число, до 65536 – двома, до 16777216 – трьома. Звідси перше рішення:

Створюємо 4 масиви, в одному зберігаємо числа по 1 байти, в іншому по 2, в третьому по 3, а що в четвертому, пропоную здогадатися самостійно.

Бавовна, і вже ми економимо. Але навіщо залишатися на досягнутому? Давайте будемо використовувати 32 масиви! І зберігати числа по 1, 2... біта. Стало ще економніше.

З іншого боку, що є масив? Це покажчик на блок пам'яті (8 байт), довжина і для C# ще пам'ять сам об'єкт масиву (20 байт).Разом, кожен масив нам обходиться в 32 байти (насправді, в C# об'єкт займає мінімум 24 байти з кроком по 8, з яких 20 б на об'єкт, а 4 - на те що залишилося або тупо на вирівнювання). Тут і далі розрахунки для 64-бітної системи. Для 32 біт покажчики в 2 рази менше, вирівнювання також на 4, так що майже все економніше в 2 рази.

Навіщо цей пасаж? До того, що 32 масиви зжеруть у нас 1КБ пам'яті просто на себе. Що із цим робити? А все просто: зберігатимемо ці 32 масиви в одному масиві!

У першому елементі зберігаємо довжину однобітного масиву, потім сам масив, потім довжина двох біт тощо. В результаті, всього 32 байти накладних витрат та ефективне зберігання.

Допитливий читач (завжди подобалася ця фраза) може помітити деяку проблему: для зберігання чисел з одного біта ми спочатку витратимо 2 біти на довжину (0, 1 або 2), а потім 2 біти на самі числа. Адже можна витратити всього 2 біти: перший біт — чи є 0, другий — чи є 1.

Ми щойно придумали бітову карту. Можна сильно не паритися і зберігати числа від 0 до 255 цим методом є число - 1, ні - 0. І витратити на це 32 байти (8 біт в байті * 32 = 256). Звичайно, з кожним новим значенням ефективність картки починає падати. Тобто. для зберігання всіх інтів нам потрібно 536870912 байт ... Якось забагато. Отже, коли зупинитися: на 256, на 16, на 65536 залежить від даних. Нехай буде 256. Мені подобається це число, гарне.

Тобто. перші 256 чисел зберігаємо бітовою картою, далі зберігаємо довжину чисел певної довжини в бітах і числа.

Але дивіться, що виходить: числа від 0 до 511 вимагають зберігання 9 біт. У той же час ми числа від 0 до 255 — ми вже зберегли. Тобто. в діапазоні 9 біт не може потрапити число 12.Лише 256 і більше. Так навіщо їх зберігати 9 бітами, якщо можна зберігати число від 0 до 255 і потім додати в розумі 256, що бракує. Заощадили ще один біт! Звичайно кожен наступний діапазон теж буде економнішим на 1 біт. Ми молодці!

Що ще можна зробити? А можна подивитись на дані. Якщо вони дуже щільні (1,2,3,5,6), можна зберігати не самі числа, а ті, яких немає (4). Тобто. замість зберігання умовних 5 чисел будемо зберігати одне. Просте правило: більше половини є - зберігаємо ті, яких немає, інакше навпаки. Де зберігати? А у довжині! Дивіться: щоб зберігати числа довжиною в 10 біт, нам потрібно 11 біт (бо від 0 до 1024 включно). Але при цьому значень в 11 біт можна засунути 2048, а використовуємо ми лише 1025. От і зберігатимемо: позитивна довжина — зберігаємо числа. Негативна - зберігаємо те, чого немає. Детальний розрахунок пропоную зробити читачеві самому як самостійна вправа (бо я не впевнений, що все зійдеться, так що вдаю, що так і треба).

В результаті ми отримали: масив, в якому перші 16 байт бітова маска наявності чисел від 0 до 255, далі - довжина із зазначенням - зберігаємо числа або їх відсутність, самі числа, бітова довжина для наступного і т.д.

Після того, як ви це реалізуєте, та ще й без помилок, думаю, ви подаєтеся прямо в дурню, наступні програмісти, які намагаються зрозуміти цей код - відправляться за вами слідом. Тож давайте спробуємо ще варіанти.

Думаємо над порядком

Дивіться. Ми маємо масив. Що в нього є, на відміну від багатьох? А є в нього порядок елементів. Це додаткова інформація, а ми її ще ніяк не використали. Що можна з цим зробити?

А можна зберігати не самі елементи, а різницю між ними:

Тобто.перший зберігаємо як є, другий - додаємо значення першого до другого і т.д. Що це нам дає? А те, що якщо ми заздалегідь відсортуємо масив, то в нас значення в ньому стануть в цілому меншими, і їх можна зберігати меншою кількістю біт.

З іншого боку, ми за умовою завдання — всі елементи різні, тобто. ми від різниці можемо ще відняти одиницю, щоб заощадити бітики:

Це нескладно, тому чому б і ні.

Але тепер виникла проблема. Т.к. ми тепер не можемо зберігати числа незалежно, а тільки в тому ж порядку, то спосіб з масивом та довжинами вже не підходить. Потрібно вигадувати щось інше, т.к. усі числа повинні зберігатися по порядку.

Зберігаємо довжину числа бітах перед самим числом

Непоганий варіант. Число займає від 1 до 32 біт, тобто. на довжину нам треба 5 біт, а потім саме число. Можна для зручності відсікати крайні випадки (ну чо ми там заощадимо? копійки!), або навпаки, виділяти їх особливо - наприклад, якщо довжина 0 - значить число 0, якщо довжина 1 - число - 1, якщо довжина 2 - то наступні 2 біта число 2,3,4,5 (ми знаємо, що можемо зрушувати те що, може бути) тощо.

А може зберігати довжину числа?

Variable-length quantity

Як би не ми перші ставимося до цього питання, тому є стандартне рішення. Використовується для зберігання рядків у UTF-8 і багато де ще. Сенс простий.
Якщо число від 0 до 127 включно - зберігаємо його 1 байтом (хоча використовували лише 7 біт). Якщо більше, то ставимо 8-й біт в 1 і використовуємо наступний байт аналогічним чином (7 біт, не вистачає прапорець і наступний). Тобто. малі числа будуть зберігатися одним байтом, трохи більше - двома, і так до 5.

Ви можете сказати - фуу ... ми щойно з бітами грали, а тут байти пішли, не круто! Так, не круто, з іншого боку, працювати з байтами все-таки простіше ніж з бітами, трохи менше економія, зате вища швидкість роботи і зрозуміліший код. Але... витрачати по биту в байті якось не дуже круто, може їсти рішення краще?

Використовуємо значення як прапори

Пропустимо всі міркування і одразу визначимося. Зберігатимемо наступним чином:

• числа від 0 до 252 зберігатимуться одним байтом. Якщо більше, то:
• якщо число від 252 до 252 + 256 = 508 ставимо значення 252, а в наступному байті число - 252 (так-так, ми вже вміємо зрушувати значення)
• якщо від 252+256 до 252+256+65536, ставимо 253 і використовуємо наступні 2 байти для зберігання самого числа - непотрібну різницю
• якщо від 252+256+65536 до 252+256+65536+16777216, ставимо 254 та 3 байти
• інакше - 255 і 4 байти.

Висновок

Ми розглянули основні способи заощаджувати пам'ять (насправді, у мене вичерпалася фантазія, але визнаватись у цьому не буду). Дані техніки можна комбінувати, використовувати інших завдань, доопрацьовувати під ситуацію. Яка техніка в результаті краще? Все залежить від ваших даних. Беріть їх та спробуйте. Добре, що не треба реалізовувати все повністю відразу. Можна просто написати код, який просто оцінить довжину. А після оцінки вже реалізовувати те, що вам сподобалося.

Не варто забувати і про швидкість цієї справи: чи готові ви витрачати багато часу на підготовку даних або на отримання. Чи варто розпочинати боротьбу з бітами, чи нижче байтів опускатися не варто. Чи достатньо оптимізувати часті ситуації, залишивши поодинокі з неефективною реалізацією. Чи можна залежно від даних використовувати різні способи зберігання (наприклад, до 8 байт тупо зберігати масиві, т.к.побічні витрати зжеруть весь виграш, та якщо з 1 байти — взагалі зберігати у псевдомассиве з одного елемента, тобто. у самому числі).

Також кілька слів про стиск: тут воно буде не дуже ефективним. Алгоритм стиснення дуже подобаються повторення, а тут їх не дуже багато. Якщо взяти умовний Zip, який складається з LZ77 + Huffman, навряд чи щось корисне вийде за допомогою LZ77, але Huffman може спробувати заощадити байти. Виходить, Zip буде марним наполовину. А ось швидкість просадить дуже і дуже сильно.

Ще зовсім не розглянуті ситуації, коли ми знаємо про те, що у нас безлічі і ми можемо зберігати їх усіх разом, використовуючи різні зрізи. Тут я зізнаюся - не впевнений, що це вийде. Відразу я не вигадав варіанти. Натомість зрозумів, що буде складно. Утім, у вас можуть бути інші думки.

Так що ділитеся ідеями в коментарях, може я пропустив якогось очевидного слона, який дозволить заощадити ще більше байт і отримати такий результат, що домогосподарки з реклами миючого засобу (якого достатньо однієї краплі) нам усім заздрити!

напишіть максимальні та мінімальні числа, які можна записати в 16-бітну змінну цілого знакового типу

Якщо ви маєте на увазі безперервний діапазон, то верхня межа буде вдвічі менша за 32767. Оскільки всього можна закодувати 65536 різних значень.

Destino Штучний Інтелект (331540) Якщо безперервний - то так. Тоді я написав би від -32768 до 32767. Але якщо діапазони окремі, то для позитивних він від 0 до 65535.

У 16-бітну змінну можна записати 216 різних значень. Зазвичай зберігання знака відводиться 1 біт, отже на кодування чисел залишається 2^15=32768 значень. Отримуємо мінімальне -32768, максимальне +32767 (на одиницю менше, тому що "перше" число - нуль).

Однак, якщо дивитися ширше, то рішення залежить від способу кодування, від того, як ми інтерпретуватимемо вміст комірки пам'яті. І тут граничні значення може бути іншими.