Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Лінейны пошук]
[Патрык Шмід, Гарвардскі універсітэт]
[Гэта CS50.] [CS50.TV]
Пошук з'яўляецца тое, што вы, верагодна, часцей, чым вы думаеце.
Відавочна, што кожны раз, калі вы адкрываеце вэб-браўзэр
і пошуку на вэб-старонцы -
Або шукаць сяброў на вашай каханай сацыяльнай сеткі -
Вы шукаеце.
Але гэта толькі малая частка пошукаў, што вы робіце на штодзённай аснове.
Калі вы хочаце, каб знайсці, што адна сіняя кашуля ў шафе,
або што ідэальны чырвоную блузку з гэтай нагоды,
Вы шукаеце.
Калі вы ідзяце ў краму, вы ніколі не былі раней,
і вы шукаеце брокалі ў праходзе прадукты
Вы шукаеце.
Тое, што вы, магчыма, пачалі заўважаць
з'яўляецца тое, што ў залежнасці ад таго, што вы шукаеце
або як элементы арганізаваны, калі вы шукаеце для іх
ён мае ўплыў на як вы будзеце шукаць.
Напрыклад, калі вашы кашулі вісяць у шафе,
Вы, верагодна, можа проста забраць яго без доўгіх пошукаў.
Калі вы мяркуючы, што вы павінны ісці да алтара
Для атрымання брокалі, вы, верагодна, павінны глядзець на ўсе іншымі гароднінай
перш, чым вы выявіце, што брокалі.
Лінейны пошук з'яўляецца прыкладам аднаго з такіх метадаў пошукаў - ці алгарытм.
Як вынікае з назвы,
Гэты метад шукае элемент у лінейным парадку, адзін за адным.
Так што, калі вы глядзіце на вынікі вашай каханай пошукавай сістэмы
а вы чыталі ў спісе вынікаў,
Вы выкарыстоўваеце лінейны пошук.
Добра. Давайце паглядзім на прыкладзе.
Скажам, у нас ёсць спіс лікаў - 2, 4, 0, 5, 3, 7, 8, і 1 -
і мы шукаем лік 0.
Відавочна, што вы можаце проста бачыць, што 0 знаходзіцца ў трэцяй пазіцыі.
Але, кампутарная праграма не так пашанцавала.
Ён можа толькі "убачыць" адно колькасць за адзін раз.
Так, пачынаючы з пачатку спісу,
гэта толькі "бачыць" 2.
Затым праграма правярае - знаходзіцца ў 2 роўная 0?
Відавочна, што не. Такім чынам, яна ідзе на наступны нумар, 4.
Ці мае 4 роўныя 0? Няма.
Наступны, 0. Ах! Нулявая роўная 0.
Там у нас гэта ёсць! Гэта ў трэцюю пазіцыю.
Добра. Давайце паглядзім на некаторыя псевдокод.
Гэта ўсяго толькі пару радкоў, але давайце глядзець на гэта па адным радку за раз.
Па-першае, давайце вызначым функцыю - і мы будзем называць яго лінейны пошук -
і яна прымае два аргументу - ключ і масіў.
Галоўнае тое, што значэнне, якое мы шукаем,
так што і ў папярэднім прыкладзе, які быў нулявы.
Масіў ўяўляе сабой спіс нумароў
, Які мае ўсе каштоўнасці, якія мы збіраемся шукаць.
Такім чынам, што мы хочам зрабіць, гэта мы хочам, каб глядзець на -
з усіх пазіцый, таму, пачынаючы з самага пачатку масіва
Сезам самага канца масіва - так што даўжыня масіва -
глядзець на кожную пазіцыю і праверыць кожны з іх.
Дык вось што, што "за" пятля робіць.
І на кожнай пазіцыі, мы збіраемся сказаць
"Гэта значэнне ў гэтым бягучая пазіцыя роўная ключ, які мы шукаем?"
Так што - і ў папярэднім прыкладзе зноў, ключ быў 0 -
такім чынам, мы кажам "гэта масіў у пазіцыі я роўная нулю?"
Калі гэта так, мы збіраемся вярнуць "я", таму што гэта бягучае становішча мы знаходзімся.
Так, у папярэднім прыкладзе,
, Якая была трэцяй пазіцыі.
Калі мы прайшлі праз увесь масіў
і мы не знайшлі нічога -
так што давайце казаць, што мы шукалі нумар 500
якія відавочна не быў у гэтым прыкладзе -
Мы павінны вярнуць тое,
і мы збіраемся вярнуць -1.
І мы проста вяртаецца -1, паколькі гэта становішча
, Якое не існуе ў масіве.
І так, што значыць, калі вы атрымаеце яго назад з функцыяй
ён кажа: "Хм, добра. Думаю, я нічога не знайшоў.
Так што 500 ніколі не быў там. "
Добрая рэч аб лінейнага пошуку з'яўляецца тое, што
яна будзе працаваць на любым спіс элементаў,
незалежна ад таго, як элементы ўпарадкаваныя.
Гэта не мае значэння, дзе брокалі ў прадукты праходу.
Пакуль вы ісці да алтара з пачатку да канца,
Вы абавязаны знайсці яго,
мяркуючы, што крама не скончылася брокалі, вядома.
Але гэта найвялікшая сіла таксама, што гэта самая вялікая слабасць.
Скажам, у вас ёсць спіс двухсот нумароў
, Якія сартуюцца ад 1 да 200.
Калі вы шукаеце нумар 198,
Вы павінны шукаць амаль увесь спіс нумароў
перш чым вы знойдзеце той, які вы шукаеце.
Там павінна быць лепш!
Будзьце ўпэўненыя, што ёсць.
Але гэта ўжо тэма для іншага відэа.
Акрамя таго, не хвалюйцеся!
Проста таму, што лінейны пошук не самае лепшае рашэнне ў любой сітуацыі,
гэта не значыць, што яно не спатрэбіцца.
У адваротным выпадку, як бы вы выявілі, што брокалі ў праходзе прадукты?
Мяне клічуць Патрык Шмід, і гэта CS50.
[CS50.TV]