Преглед рада низова

У рачунарству постоји концепт линеарне структуре података , што значи да су подаци структурирани на линеарни начин на који је редослед важан . Постоје низови и повезане листе , али данас ћу говорити углавном о низовима и мало о повезаним листама.

Већина језика објекта оријентисане долазе са низова , док је већина м унцтионал језика долазе са повезаним листама (види зашто још једну од својих чланака, помиње на дну овог чланка).

Постоји добар разлог за ову диференцијацију у који ћемо касније ући. За сада хајде да само на брзину погледамо разлике између две структуре података. Да бисмо то урадили, мораћемо да путујемо траком за памћење.

Време премотавања

Предмети и функције и све што знамо о рачунарима, у основи се чувају у битовима и бајтовима у рачунару.

У језицима као што су Јава и Ц, претходно морате изричито навести величину низа.

Чекај, али Руби то не ради?

У Руби-у користимо Arrayлинеарне структуре података. Можемо додати наизглед бесконачне ствари у Руби-ов низ и то не би било важно што се нас тиче.

То је сјајно зар не ?! То значи да су низови бескрајно велики, зар не? А да је Руби супериоран језик? Срећни смо!

Али не тако брзо. * искочи ваш балон *

Не постоји низ бесконачних величина; оно што видите у Руби-у је оно што називамо динамичким низом и то кошта.

Да бисмо разумели шта су динамички низови, погледајмо прво како су низови представљени у меморији. Пошто се МРИ Руби (Матз 'Руби Интерпретер) компајлира до Ц кода, погледаћемо како су низови представљени у Ц.

Ц-инг верује

Заронит ћемо у мало Ц кода да нам помогне мало боље Ц ... :)

У језицима нижег нивоа, попут Ц, морате сами да се бавите показивачима и додељивањем меморије. Чак и ако се раније нисте бавили Ц (д изјава - нисам ни ја ), можда сте Ц-еен један од најпознатијих (не) примера у наставку:

Раздвојимо овај бит кода:

  • malloc нема магично значење иза себе, буквално се залаже за memory allocation
  • malloc враћа показивач
  • malloc узима аргумент, а то је величина меморије коју желите да вам програм додели.
  • 100 * sizeof(int) говори програму да желимо да сачувамо 100 целих бројева, па нам доделите 100 * величину онога што би заузимало свако целобројно.
  • ptr/ показивач чува референцу на меморијску адресу.

Тимми чува пртљаг!

Ако горњи пример заиста није имао смисла, покушајте са овом аналогијом. Додељивање меморије схватите као вратар пртљага. Ради овако:

  • Тимми одлази до шалтера, каже рецепционару да има 2 комада пртљага, отприлике овако велик, и да би желео да их ускладишти у остави.
  • Вратар погледа складишну просторију и каже "Да, имамо собу на за то предвиђеном B4месту и тај простор ћемо доделити за одлагање вашег пртљага".
  • Они у нашем случају предају Тиммију картицу за преузимање са назначеним B4местом.
  • Тимми је срећан, обилази около радећи било шта, а када жели да узме свој пртљаг, враћа се до шалтера и показује им своју картицу за преузимање . „ Да ли сте узели мој пртљаг?

У нашем примеру, Тимми-ов пртљаг су подаци , картица за преузимање је показивач (наводи се где је Тимми-јева торба ускладиштена). Место на којем рецепционар чува Тимми-јеву пртљагу је меморијски блок , а бројач програм .

Показујући бројач ( програм ) Тимми-јеву картицу ( показивач / адреса меморије ), Тимми може преузети свој пртљаг ( податке ). Бонус? Будући да тачно знају где се чува Тиммијева торба - B4, то значи да релативно брзо могу да преузму сву Тиммијеву пртљагу!

Такође, да ли сте се икад запитали зашто тако приступате елементима у низу са индексом ?

То је зато што низ садржи референце на меморијски блок, а индекс му говори одмак .

Аналогија за то је ако вас замолим да потражите Тиммија у реду од 20 људи, логично бисте морали питати сваког од њих да ли су Тимми. Али, ако сам вам рекао да је Тимми 6. ( индекс ) од првог лица ( ваш оригинални показивач ), тачно знате где треба тражити.

Управо због тога је преузимање елемената у низовима брзо - програм не мора да прегледа свих 100 елемената да би пронашао оно што тражите. Ако имате индекс, он мора само да дода помак оригиналној меморијској адреси и дроид којег сте тражили биће одмах тамо!

Шта су онда динамички низови?

Дакле, рекао сам вам мало о томе како су низови представљени у меморији, али сада је време да разговарамо о неким минусима.

Сећате се како морате изричито да пријавите потребну количину меморије? То значи да ће низ пронаћи место које ће тачно одговарати вашој величини. Не постоји гаранција да ће моћи да стане више од онога што имате (јер би меморијски блок одмах иза њега могао бити заузет).

Вратимо се на нашу аналогију пртљага: мислите на то као да би Тимми требао да ускладишти 2 комада пртљага и B4може да ускладишти тачно 2 комада пртљага, тако да их додељују Тиммију. Сад из неког разлога Тимми жели да ускладишти још један комад пртљага, али B4не може да ускладишти 3, само 2 комада, па шта раде?

Узимају сав његов постојећи пртљаг, премештају га на ново место у које може да стане више од 3 комада, а затим их све заједно чувају.

То је скупа операција, али тачно тако функционише и меморија!

У Руби-у не морате да декларишете одређену величину пре него што то учините , али то је зато што Руби аутоматски обрађује то за вас помоћу динамичких низова.

Оно што динамички низ ради је да ће се, ако се низ приближи свом пуном капацитету, аутоматски прогласити новим, већим низом и у њега преместити све постојеће елементе, а стари низ ће се потом сакупљати. Колико већи? Фактор раста је обично 2; двострука величина тренутног низа.

У ствари, не верујте ми на реч .

Руби има ОбјецтСпаце модул који нам омогућава интеракцију са тренутним објектима који живе у меморији. Помоћу овог модула можемо завирити у употребу меморије нашег динамичког низа - звучи тачно онако како желимо!

Написао сам малу Руби скрипту која израчунава фактор раста динамичког низа. Слободно га погледајте овде, а ако јесте, можете видети да Руби-ови низови имају фактор раста 1,5к (то јест, они чине низ који је 50% већи на свакој копији).

Знам шта су низови, шта су повезане листе?

Имајте на уму да иако се низови и повезане листе сматрају линеарним структурама података, они имају једну велику разлику између себе.

Елементи у низу чувају се буквално тик један поред другог у меморији (тако да можемо имати индекс за брза претраживања). Али чворови на повезаним листама немају таква ограничења (због чега не постоји претрага индекса за повезане листе) - свака ставка може се сачувати било где у меморијском блоку.

Готово као да Тимми покушава да ускладишти 5 комада пртљага, а вратар нема места и одлучује да их остави свуда. Звучи неорганизовано?

Такође, ако се чувају на различитим местима, како знате које су вреће Тиммијеве? Савет: Само пратите следећи чвор / торбу! У нашем случају, вратар их чува одвојено, али са ознаком на свакој од њих која упућује на следећу торбу.

Чвор на повезаној листи састоји се од два дела - дела података и показивача на следећи чвор. Тако су у стању да одрже linearдео тога - они и даље имају концепт реда, само их не треба дословно чувати у реду!

node = [ data | pointer ]

На пример, с обзиром на следећи пример ускладиштен у меморији:

[C | D] [A | B] [B | C] [D | nil]

Изгледа да ови делови нису у реду - али да сам вам рекао да је први елемент A, могли бисте ми рећи тачан редослед листе:

list = [A -> B -> C ->Д -> нула]

Постоји много занимљивих ствари које можете да урадите са повезаним списковима у које овде нећу залазити (такође много на Биг О о којима нисам говорио). Али већ постоји мноштво добрих чланака о структурама података. Ако сте успели овде, предлажем вам да прочитате са Алијевог блога овде.

хвала у, следеће: увод у повезане листе

У овом посту ћемо говорити о структури података повезане листе на језику "хвала у реду" од ... дев.то

Такође можете прочитати више о Лист / Цонс на Вики овде.

Завршна напомена

У почетку сам овај чланак написао за мало другачију тему - [Еликсир | Зашто повезане листе?], Али открио сам да је требало предуго да објасним како низови функционишу пре него што сам успео да објасним зашто Еликир користи повезане листе. Тако да сам их раздвојио у два чланка.

У том чланку говорим о томе зашто функционални језици користе повезане листе као своју линеарну структуру података. Погледајте!

[Еликсир | Зашто повезане листе? ]

Одувек сам мислио да су структуре података у реду, али знате ли шта је хладније? Видевши их у дивљини! Док пролазим кроз ... од

Извори

  1. //медиум.цом/@ребо_доод/руби-хас-а-мемори-проблем-парт-1-7887ббацц579 - Овде сам сазнао за додатне ObjectSpaceметоде захтевајући их

Првобитно објављено на дев.то