ハッシュ法 オープンアドレス ダブルハッシング法
ハッシュ法は検索アルゴリズムの一つ。 各データ(keyと呼ぶ)の挿入するべき位置をハッシュ関数を用いて求める。 ハッシュ関数で求めた値、ハッシュ値が配列の挿入するべき位置(インデックス)を示す。
ハッシュ関数 Hash(key)=key mod m ここでmをテーブルサイズとする。
弱点は、ハッシュ関数を用いて求めた値が以前に求めた値と重複する場合がある。 この時に、ダブルハッシュ法を用いる。 ダブルハッシュ法は、ハッシュ関数に一回目のハッシュ値とは別のテーブルサイズmのハッシュ関数を含めた関数 関数は、 H(key) = (h1(k) + j*h2(k))%m ここで、 h1(k) = key mod m h2(k) = 1 + key mod n n: mとは異なる値 j: 1(今回の場合) とする。
また、重複した場合にh1(k)からh2(k)分だけ位置を移動させることになることから、mとh2(k)が互いに素でないと挿入出来ない位置が生じます。これはmを素数としてh2(k)をmより小さい値にすることで回避することができる。
参考資料
クローラーの写経してみた
前からクローラー作ってみたいなって思ってたけど、なかなか余裕がないし設計アイデアが浮かばなかったからとりあえずググってみたらわかりやすいのが見つかった。 How to make a web crawler in JavaScript / Node.js とりあえず完璧に写経しただけやけど、非常にシンプルで考え方がわかりやすかった。 ここからさらに外部リンクまで検索してくれるようにアップデートしてみたいな。
var request = require("request"); var cheerio = require("cheerio"); var URL = require("url-parse"); var START_URL = "http://www.arstechnica.com"; var SEARCH_WORD = "stemming"; var MAX_PAGES_TO_VISIT = 10; var pagesVisited = {}; var numPagesVisited = 0; var pagesToVisit = []; var url = new URL(START_URL); var baseUrl = url.protocol + "//" + url.hostname; pagesToVisit.push(START_URL); crawl(); function crawl() { if (numPagesVisited >= MAX_PAGES_TO_VISIT) { console.log("Reached max limit of number of pages to visit."); return; } var nextPage = pagesToVisit.pop(); if (nextPage in pagesVisited) { // We've already visited this page, so repeat the crawl console.log("Run the crawler again"); crawl(); } else { // new page we haven't visited console.log("pagesVisited: ", pagesVisited, nextPage); visitPage(nextPage, crawl); } } function visitPage(url, callback) { // add page to our set pagesVisited[url] = true; numPagesVisited++; // make the request console.log("candidates... ", pagesVisited); console.log("Visiting page " + url); request(url, function(error, response, body) { // check status code (200 is HTTP OK) console.log("Status code : " + response.statusCode); if (response.statusCode !== 200) { callback(); return; } // Parse the document body var $ = cheerio.load(body); var isWordFound = searchForWord($, SEARCH_WORD); if (isWordFound) { console.log("Word " + SEARCH_WORD + " found at page " + url); } else { collectInternalLinks($); // in this short program, our callback is just calling crawl(); callback(); } }); } function searchForWord($, word) { var bodyText = $("html > body").text(); return bodyText.indexOf(word.toLowerCase()) !== -1; } // search internal links function collectInternalLinks($) { var relativeLinks = $("a[href^='/']"); console.log("Found " + relativeLinks.length + " relative links"); relativeLinks.each(function() { pagesToVisit.push(baseUrl + $(this).attr("href")); }); }
転職しました！
転職してからしばらく時間が経ったのでダラダラと転職記について更新します。
前回投稿した時は、まだ転職活動中でした。当時は相変わらず転職活動のために面接、コーディングテスト、プログラミングコンテストに参加などして慌ただしい毎日を過ごしていました。 結論から申し上げると、７社から内定を頂くことができ、そのうちの１社であるサンフランシスコ発のIT会社MightyHiveの内定を承諾することにしました！理由はこの会社がAdTech業界の最先端にいること、上司が他の会社（日本企業）に比べてserving managementを意識しており仕事に極力関係のないストレスをためずに効率良く仕事ができそうであること、AdTech業界というまだまだ成長中の業界でエンジニアとしてのキャリアを築くことで業界の最先端に立てる可能性があること（特に日本ではまだまだ若い業界）、アメリカの企業風土を経験できること、海外コミュニティや業界関係者とのネットワーキングができることなどのメリットがあると考えたからです。
毎日激務で仕事の後や週末も勉強することがたくさんありますが、徐々に人脈も形成できており楽しく仕事しています。今後はもう少し気持ちと時間に余裕が出てくるようであれば、Web開発に止まらずハードウェア開発やRTB(Real Time Bidding)のシステム開発、パブリックスピーチやMeetupの開催などにも挑戦してみたいところです。 さらに時間が出来次第、前から習得したかった修士号取得にも挑戦したいところです。
Python error message: There was a problem confirming the ssl certificate: [SSL: TLSV1_ALERT_PROTOCOL_VERSION] tlsv1 alert protocol
ERROR: There was a problem confirming the ssl certificate: [SSL: TLSV1_ALERT_PROTOCOL_VERSION] tlsv1 alert protocol
If you got this error message, update your pip at first.
Update pip with curl https://bootstrap.pypa.io/get-pip.py | python
Could not fetch URL https://pypi.python.org/simple/google-cloud-storage/: There was a problem confirming the ssl certificate: [SSL: TLSV1_ALERT_PROTOCOL_VERSION] tlsv1 alert protocol version
Why? What's going on? Python org decided to stop supporting TLS, that is, macOS user who use version Sierra or older version needs to upgrade to pip(9.0.3) by yourself.
Reference:
SeleniumとChromedriverを使ってみた
web developerのJD見てるとわりとSeleniumの使用経験について問われてることが多かったこともあり、前から気になっていました。
Pythonで書きたかったのでSeleniumもPython bindingsをインストールしました。
まず最初は
pip install selenium
しましたが、ここで早速詰まって
There was a problem confirming the ssl certificate:
とエラーが吐かれてました。
pipのバージョンに関する問題かななどと調べて見ましたがイマイチ適切な原因が見つからなかったのでファイルダウンロードすることにしました。
そしてwebdriverのインストール、webdriverはブラウザと同じpathにないといけない点を気をつけないといけません。
僕の場合は/usr/bin/の直下でした。
ただwebdriverのインストールした時も問題が。
mvコマンド使ってdriverファイルを移動させようとしたものの
mv: rename chromedriver to ../../../usr/bin/chromedriver: Operation not permitted
のメッセージが。 どうやらセキュリティ機能によってSystem Integrity Protectionが発動したことが原因でした。 この辺は「system integrity protection disable」とかググったらmacのサポーターたちが丁寧な回答を出してくれています。 ここまできたらあとは例を試すことができました。
import time from selenium import webdriver # Optional argument, if not specified will search path. driver = webdriver.Chrome('/usr/bin/chromedriver') driver.get('http://www.google.com/xhtml') time.sleep(5) # Let the user actually see something! search_box = driver.find_element_by_name('q') search_box.send_keys('ChromeDriver') search_box.submit() time.sleep(5) # Let the user actually see something! driver.quit()
を走らせた時に自動でブラウザが起動して、検索窓にChromeDriverを打ち込み検索結果を表示その５秒後にブラウザ閉じるという動作をさせますが 今までしたことができるようになるのはやはり楽しいし感動しますね！ しばらくSeleniumで遊んでみます。
Reference:
GitHub - SeleniumHQ/selenium: A browser automation framework and ecosystem.
Selenium Client Driver — Selenium 3.14 documentation
「SQL 第2版 ゼロからはじめるデータベース操作」読みました
割と時間に余裕が出てきたから以前から積ん読してたうちの一冊を読みきりました。 SQL 第2版 ゼロからはじめるデータベース操作 この本の良い点は、紹介されたクエリを実際にデータベースを作って試せる点ですね。さらにMySQL, Postgers, Oracle, SQLServerなど多種多様なDBMSに沿った書き方を比べることができるので、それぞれの違いを確認することもできます。
ぼくがこの本読んで新しく発見したことはwindow関数とgroupingの使い方ですね。おそらくweb developerしている限り普段の業務でクエリがっつり書くことがあるのかは知りませんが、まあ知ってるに越したことはないので良い経験になりました。
I just finished reading a book related to SQL. The good points of this book is that you can try queries which you learned with making a database with several DBMS such as MySQL, Postgers, Oracle, SQLServer so that you can find the different styles of writing. What I learned this time is how to use window function and grouping. As long as I work as a web developer, I might not have chances to write complicated qeries. However that was the good chances to expose myself to know these ways of writing queries.
国名しりとり countries' name caterpiller
頭の体操という事でしりとりしました。 問題の条件は以下です。 与えられた国名リストでしりとりをします。最長を求めよ。
const list = [ "Brazil", "Cameroon", "Chile", "Greece", "Uruguay", "Italy", "France", "Bosnia and Herzegovia", "Germany", "USA", "Russia", "Croatia", "Spain", "Australia", "Cote D'Ivoire", "Costa RIca", "Switzerland", "Honduras", "Iran", "Portugal", "Belgium", "Korea Republic", "Mexico", "Netherlands", "Colombia", "Japan", "England", "Ecuador", "Argentina", "Nigeria", "Ghana", "Algeria" ]; function makeLowerCase(countries) { return countries.map((elem) => elem.toLowerCase()); } // make a loop to connect each tale of a word and beginning of a next word as long as possible, if it is not possible to connect from the rest of the list, then finish and push into the empty array. function findMaximumLength(countries) { const result = []; const countriesList = makeLowerCase(countries); for (let i = 0; i < countriesList.length; i++) { const copyList = countriesList.slice(); copyList.splice(i, 1); result.push(search([countriesList[i]], copyList)); } // look for result array and find a maximum const sortedlist = result.sort((first, second) => second - first); return sortedlist[0]; } const search = (currentList, candidateList) => { for (let i = 0; i < candidateList.length; i++) { if ( currentList.slice(-1)[0][currentList.slice(-1)[0].length - 1] === candidateList[i][0] ) { currentList.push(candidateList[i]); candidateList.splice(i, 1); search(currentList, candidateList); } } return currentList.length; }; console.log(findMaximumLength(list));
答えは８です。 他にもっと簡単に解く方法があるのかもしれませんが、とりあえずこれが思いついたアプローチです。
Exercise time! The restrictions are below. Find the longest length of a caterpillar. I found a recursive way that always iterates through the rest of the countries which have never been selected. However, if there might have other approaches, and in that case please share with me. In addition, the answer is 8.
