Що таке складність майнінгу? На прикладі Bitcoin. Оцінка складності алгоритмів або Що таке О(log n) Складність версія

Що таке складність майнінгу? На прикладі Bitcoin.

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

Що означає термін «складність майнінгу».

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

Одна з особливостей криптовалюту – це дефляційний характер. Це означає, що сукупна кількість здобутих монет неспроможна перевищувати задане програмним кодом число. Наприклад, максимальна кількість біткоїнів дорівнює 21 мільйон монет. Причому останній біткоїн буде здобутий лише 2140 року. Незважаючи на кількість майнерів, кожні 10 хвилин видобувається лише 12,5 BTC. Ці монети розподіляються між майнерами відповідно до витраченої обчислювальної потужності. Нагорода за підписаний блок не збільшується (а раз на чотири роки навіть скорочується наполовину). І якщо кількість майнерів зростає, то пропорційно зменшується дохід кожного окремого добувача. З приходом нових криптодобувачів зростає конкуренція за обмежену нагороду.

Для наочної демонстрації цієї ситуації введено параметр мережі криптовалюти «складність майнінгу». Складність майнінгу – це показник, який відображає, наскільки важко вирішити математичне завдання для підписання блоку та отримання за нього нагороди. Складність автоматично перераховується через певний проміжок часу. У кожної криптовалюти він різний. Наприклад, перерахунок складності видобутку біткоїну відбувається кожні 2016 блоків, видобуток яких займає приблизно 2 тижні. Згідно з програмним кодом, складність підлаштовується так, щоб пошук чергового блоку займав приблизно 10 хвилин незалежно від кількості майнерів та сукупного хешрейту.

Складність автоматично збільшується, якщо пошук останніх 2016 блоків зайняв менше двох тижнів. Це свідчить, що сукупна обчислювальна потужність майнінг пристроїв зросла. І навпаки, сигналом до зменшення складності стане уповільнення пошуку 2016 блоків, оскільки хешрейт усіх пристроїв скоротився. Результатом стає жорсткий контроль за швидкістю випуску нових монет.

Де знайти складність майнінгу. Складність видобування топ-10 криптовалют.

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

Актуальну інформацію про більш ніж 100 криптовалютів можна знайти на сайтах:

• https://www.coinwarz.com/charts/difficulty-charts
• https://bitinfocharts.com/ru/

* Потрібно враховувати, що складність майнінгу змінюється з часом, тому різні сайти можуть видавати різні дані про складність. Іноді різниця сягає 10-20% по валюті двох різних агрегаторах. Якщо ви шукаєте показник складності майнінгу не просто для задоволення цікавості, а для використання в практичних цілях, то орієнтуйтесь на середні цифри. Наприклад, якщо будуєте прогноз зміни складності майнінгу в майбутньому на основі історичної динаміки, то розумніше брати дані за останні півроку-рік, а не два-чотири тижні.

** Ряд криптовалют неможливо майнути у традиційному сенсі. Одні використовують POS-майнінг, при якому на монети, що лежать у гаманці, періодично нараховуються відсотки. Для POS-майнінгу не потрібно купувати спеціалізоване обладнання та витрачати гроші на електрику. Інші криптовалюти (наприклад, Ripple) вже повністю видобуті і лише перерозподіляються між власниками.

Складність майнінгу: на що впливає та чому зростає.

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

Наприклад, асик для видобутку біткоїну antminer s7 у середині 2017 року (а точніше при складності на 1 липня 2017 року) видобував 0,06 BTC на місяць. Але складність мережі біткоїн безперервно зростала. За даними на 1 листопада 2017 року це обладнання добуде вже 0,026 BTC за місяць. Дохід майнера лише за 4 місяці просів більш ніж наполовину.

Але навіть щотижневе скорочення доходу не робить інвестиції у майнінг менш привабливими. Почасти виторг у криптовалюті компенсується зростанням обмінного курсу до фіату. У нашому прикладі 1 липня курс біткоїну дорівнював 2.400 $, а вже 1 листопада котирування зросли майже до 6.700 $. Виходить, що доходи майнерів у фіаті збільшилися навіть попри швидке зростання складності видобутку.

У цьому полягає логіка творців криптовалют із динамічною складністю. І хоча прямої залежності між ціною валюти і тим, наскільки важко її добувати, ні, все ж таки є непрямий взаємозв'язок. Передбачається, що зростання складності означає збільшення популярності криптовалюти у широких масах населення. Хтось із тих, хто дізнався про децентралізовані валюти, спробує майнути. Це спричинить зростання складності. Але в той же час з високою ймовірністю зросте попит, а отже, і курс. Виходить, що зростання інтересу в суспільстві стимулює одночасно і зростання курсу, і зростання складності майнінгу.

З технічного погляду показник складності майнінгу залежить від:

• хешрейта мережі (кількості та обчислювальної потужності обладнання всіх майнерів);
• швидкості видобутку 2016 блоків;

Усі три показники перебувають у прямій залежності. Зростання хешрейту мережі означає, що до майнінгу приєдналися нові учасники і конкуренція зросла. Зі збільшенням кількості майнерів час, який витрачається на пошук чергового блоку, скорочується. Після 2016 року блоку відбувається перерахунок складності видобутку. Зміна показника описується закономірністю:

Складність майнінгу біткоїну.

Зростання складності обумовлено цілою низкою факторів, які тісно взаємопов'язані:

• розвиток чіпів асиків та вихід на ринок більш продуктивних моделей;
• популяризація біткоїну та приплив нових майнерів;
• висока рентабельність інвестицій у майнінг через випереджальне зростання курсу біткоїну до долара;
• перенесення обчислювальної потужності з інших валют, котирування яких падають або ростуть повільніше за біткоїн;
• інші фактори;

Складність майнінгу біткоїну з 2016 року зросла у 5-6 разів. Зростання тривало практично безперервно. Лише у серпні 2017 року вперше за рік спостерігалося зменшення показника. Можливо, на це вплинув серпневий SegWit біткоїну, який змусив частину майнерів перенести потужності на альткоїни.

6 відповідей

Складність завжди вказується щодо конкретної змінної чи набору змінних. Тому коли стандарт говорить про постійну вставку часу, йдеться про постійний час щодо кількості елементів у списку. Тобто, O(1) вставки означає, що кількість елементів, що знаходяться у списку, не впливає на загальну складність вставок. Список може містити 500 або 50000000 елементів, а складність операції вставки буде однаковою.

Наприклад, std::list має O (1) вставки та видалення; кількість елементів у списку не залежить від складності вставок. Однак складність розподілу пам'яті може залежати від кількості речей, які вже було виділено. Але оскільки O(1) говорить про кількість елементів у списку, вона не поширюється на це. І це не передбачається, тому що тоді ми вимірюватимемо складність розподільника пам'яті, а не структуру даних.

Коротше: це інший вимір.

Це означає, що ми можемо реалізувати наш алгоритм так сильно, як нам подобається, у тому числі той, де час насправді не є постійним у будь-якому прагматичному сенсі, але де ми дотримувалися кількості "операцій" над об'єктами, що містяться.

Складність не вказана щодо реалізації. Він поставлений щодо алгоритмів. Не має значення, що контекст може перемикатися, тому що час виконання не є складним завданням.

Як і вище, ви можете реалізувати std::list за допомогою розподільника пам'яті, який є O (log(n)) щодо делецій (де n – кількість розподілів). Однак, видалення елемента в списку все одно буде O (1) по відношенню до кількості елементів у списку.

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

Складність – це інструмент для оцінки ефективності алгоритму. Складність не означає, що ви можете припинити думати.

А що саме означає "амортизація"?

Наскільки я розумію, постійна складність означає, що операція O(1) : ви можете заздалегідь сказати, скільки елементарних операцій (читання/запис, інструкції зі збирання, що завгодно) виконуватиметься. І це оцінка є спільним кордоном всім можливих станів цільового об'єкта. Тут є улов: у багатопотоковому середовищі ви не можете передбачити потокові комутатори, тому ви можете зробити деякі міркування щодо часу роботи, що минув, тільки в ОС реального часу.

Про амортизовану постійну складність, це ще слабше. Складаючи резюме відповідей, це гарантія того, що в середньому ваша операція є постійною. Це означає, що число елементарних операцій N наступних операцій O(N) . Це означає, що кількість елементарних операцій становить близько O(1), але допускає деякі рідкісні стрибки. Наприклад, додавання елемента до хвоста вектора є постійним, але іноді потрібна додаткова важка операція; має амортизований постійний час, означає, що додаткова операція виконується не так часто і займає передбачувану кількість часу, тому загальний час операції N все ще O(N) . Звичайно, тут застосовується і той самий улов.

Отже, відповідаючи на ваші запитання:

• Складні гарантії стандарту застосовуються дійсно лише до інструкцій машинного коду, необхідні виконання операції, і мають на увазі, що час виконання якимось чином обмежено. (Дійсно, донедавна на С++ навіть не було покажчика на тему, пов'язаного з мовою, тому зі стандартної точки зору С++ на той час програма була виконана на спеціалізованій С++-машині.)
• Амортизація "обмежена константою в середньому", що зазвичай відбувається у разі майже завжди постійного обмеженого часу операції з деякими досить рідкісними відхиленнями.

Edit:
Ви можете подивитись, наприклад, розділ 23.1 стандарту С++:

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

якщо кажуть, що операція має "постійну складність", насамперед це зазвичай стосується тимчасової складності. Я міг би посилатися на просторову складність, але якщо це так, то явно буде вказано нормально.

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

swap() - це постійна складність, тому що не має значення, скільки елементів знаходиться у векторі, операція займе стільки ж часу.

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

push_back() для вектора називається константою "амортизується", оскільки в нормальному випадку, коли перерозподіл не повинен відбуватися, кількість часу, яке займе операція, не пов'язана з тим, скільки елементів знаходиться у вектор вже - така ж кількість часу береться, щоб додати новий елемент до вектора нульової довжини щодо вектора довжини 10 мільйонів. Однак, якщо вектор необхідно перерозподілити, необхідно мати копію існуючих елементів, і це не постійна операція - це лінійна операція. Але передбачається, що вектор має бути сконструйований таким чином, щоб перерозподіл відбувався нечасто, щоб вони могли бути amortized протягом багатьох операцій push_back() .

але зробити push_back на векторі ще непередбачуваний. Найчастіше це буде дуже швидко, але час від часу йому доведеться перерозподіляти простір для всіх даних і копіювати кожен елемент у нове місце. Таким чином, він менш передбачуваний з точки зору часу виконання, ніж один список: push_front, але він, як і раніше, називається постійним (амортизується). У середньому додавання великої кількості даних у вектор займе складність, яка не залежить від доданої суми, і саме тому вона називається "амортизованим постійним" часом. (Правильно?)

Складність O(1) – константа (з урахуванням тимчасової складності) означає, що час завершення алгоритму не пов'язаний з розміром проблеми.

Отже, пошук значення хешированной структурі - це O (1), оскільки час, необхідне цього, залежить від кількості його значень. Однак те саме не відноситься до зв'язаного списку, тому що ми повинні сканувати значення (число яких змінюється зі збільшенням кількості елементів), щоб знайти наше значення.

У випадку 3, коли він копіює кожен елемент, це не операція O(1), а операція O(N) (але більшу частину часу це O(1), тому вона зазвичай стала). Амортизація враховує це, відзначаючи, що алгоритм зазвичай завершується в O(1) разів і рідко потрапляє у цей випадок O(N).

Напевно, ви не раз стикалися з позначеннями на кшталт O(log n) або чули фрази типу «логарифмічна обчислювальна складність» на адресу будь-яких алгоритмів. І якщо ви так і не розумієте, що це означає, це стаття для вас.

Оцінка складності

Складність алгоритмів зазвичай оцінюють за часом виконання або використовуваної пам'яті. В обох випадках складність залежить від розмірів вхідних даних: масив із 100 елементів буде оброблений швидше, ніж аналогічний із 1000. При цьому точний час мало кого цікавить: воно залежить від процесора, типу даних, мови програмування та безлічі інших параметрів. Важлива лише асимптотична складність, т. е. складність при прагненні розміру вхідних даних до нескінченності.

Допустимо, деякому алгоритму потрібно виконати 4n 3 + 7n умовних операцій, щоб обробити n елементів вхідних даних. При збільшенні n на підсумковий час роботи значно більше впливатиме зведення n в куб, ніж множення його на 4 або додаток 7n . Тоді кажуть, що тимчасова складність цього алгоритму дорівнює О(n 3), тобто залежить від розміру вхідних даних кубічно.

Використання великої літери О (чи так звана О-нотація) прийшло з математики, де її застосовують для порівняння асимптотичного поведінки функцій. Формально O(f(n)) означає, що час роботи алгоритму (або обсяг займаної пам'яті) зростає залежно від обсягу вхідних даних не швидше ніж деяка константа, помножена на f(n) .

Приклади

O(n) - лінійна складність

Таку складність має, наприклад, алгоритм пошуку найбільшого елемента в не відсортованому масиві. Нам доведеться пройтися всіма n елементами масиву, щоб зрозуміти, який з них максимальний.

O(log n) – логарифмічна складність

Найпростіший приклад – бінарний пошук. Якщо масив відсортований, ми можемо перевірити, чи є у ньому якесь конкретне значення, шляхом розподілу навпіл. Перевіримо середній елемент, якщо він більше за шуканий, то відкинемо другу половину масиву - там його точно немає. Якщо ж менше, то навпаки – відкинемо початкову половину. І так продовжуватимемо ділити навпіл, у результаті перевіримо log n елементів.

O(n 2) - квадратична складність

Таку складність має, наприклад, алгоритм сортування вставками. У канонічній реалізації він являє собою два вкладені цикли: один, щоб проходити по всьому масиву, а другий, щоб знаходити місце черговому елементу вже відсортованої частини. Таким чином, кількість операцій залежатиме від розміру масиву як n * n, тобто n2.

Бувають інші оцінки за складністю, але всі вони засновані на тому ж принципі.

Також трапляється, що час роботи алгоритму взагалі залежить від розміру вхідних даних. Тоді складність позначають як O(1). Наприклад, для визначення значення третього елемента масиву не потрібно ні запам'ятовувати елементи, ні проходити кілька разів. Завжди потрібно просто дочекатися в потоці вхідних даних третій елемент і це буде результатом, на обчислення якого для будь-якої кількості даних потрібно один і той самий час.

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