知らなかったことは、「背景中性子」が地上では観測されることです。100 [個/(m^2 s)]だそうです。
Mar 18, 2016
Mar 17, 2016
東大から見たLENR
「第 39 回 STS 研究会 2013/12/19 伊藤泰男
「常温核融合」 / 低エネルギー核反応の現状」
という資料があったので、リンクとして紹介します。
検索によれば、伊藤泰男 さんは多分東大教授だと思います。
学問や研究の自由とは、自分の時間と資金ですること。
東大教授は職業でありそこから収入を得ているのだから、
それを捨てるような発言行動を彼に期待してはいけない。
そういう前提で資料を読めば、随分と好意的に書かれていると思いました。
ちなみに、特定非営利活動法人科学技術社会研究所の資料でした。特定非営利活動法人科学技術社会研究所
「常温核融合」 / 低エネルギー核反応の現状」
という資料があったので、リンクとして紹介します。
検索によれば、伊藤泰男 さんは多分東大教授だと思います。
学問や研究の自由とは、自分の時間と資金ですること。
東大教授は職業でありそこから収入を得ているのだから、
それを捨てるような発言行動を彼に期待してはいけない。
そういう前提で資料を読めば、随分と好意的に書かれていると思いました。
ちなみに、特定非営利活動法人科学技術社会研究所の資料でした。特定非営利活動法人科学技術社会研究所
Mar 16, 2016
投資元がE-CATから手を引いた
Industrial Heat’s E-Cat Exit, March 10, 2016 – By Steven B. Krivit – (Industrial Heat has apparently terminated its relationship with businessman Andrea Rossi. ...)
というニュースが飛び込んできました。
どうやら、 Andrea Rossi 氏が主張していた性能をクリアできなかったから、投資元のIndustrial Heatが、手を引いたようです。
技術的内容はまったく不明なので、理由もはっきりしません。投資額は、$11,555,050 (10億円ぐらい)だったようです。
最も商用化に自信をみせていた、E-CATの商用化はかなたへと遠のいたのでしょうか。
というニュースが飛び込んできました。
どうやら、 Andrea Rossi 氏が主張していた性能をクリアできなかったから、投資元のIndustrial Heatが、手を引いたようです。
技術的内容はまったく不明なので、理由もはっきりしません。投資額は、$11,555,050 (10億円ぐらい)だったようです。
最も商用化に自信をみせていた、E-CATの商用化はかなたへと遠のいたのでしょうか。
Mar 5, 2016
日本人もっとお金持ちになった方がいいのでは
[現状]
世界の経済大国のランキングは、
世界の名目GDP 国別ランキング統計・推移(IMF)(2014)
から
世界の資産1100億円(10億ドル)以上の大富豪ランキング(2015)を見れば、
米国 536人
中国 213人
ドイツ 103人
インド 90人
ロシア 88人
イギリス 53人
フランス 47人
韓国 30人
台湾 33人
日本 24人
日本の大富豪が少なすぎる。自由の国アメリカだけでなく、共産主義の不自由の国、中国と比べても一桁少ないのだ。
国家のGDP経済規模から比較して、日本人大富豪の人数が、中国、インド、ロシア、韓国、台湾に及ばないのは、ひどく異常な事である。
Wikiなどを読めば、小金持ち(資産10億円以下)については、日本にもかなりいることはわかる。小金持ちは、日本の大企業のサラリーマン経営者たちに多いようだ。
[富豪が少ない日本の将来]
日本で、借金してまで新規に事業を興すことはできない。その理由は簡単だ。銀行が担保のない人間にお金を貸してくれないからだ。
バブル崩壊前までは、土地神話があり、借金と同額の土地を持っていれば融資してもらえた。土地本位制で、日本経済は、戦争後の焼け野原から驚異的に復興した。
バブル崩壊後は、土地の値段が下がり続けており、土地では担保にならず、銀行は融資できないのだ。
将来が不明確な新規事業の立ち上げは、自腹資金ですることになる。新規事業の初期投資は、最低10億円はかかる。本当の富豪(資産10億円以上)でないと、新規に事業を興すことは難しい。
日本がバブル崩壊(1991年)から停滞して韓国に追いつかれ、中国に抜き去られた本当の理由は、日本には富豪が少ないことに原因がある。
このままでは、日本が発展する速度は遅く、世界からさらに置いてきぼりにされる。
GDPと大富豪の人数の比率から、日本の経済的自由が、共産主義の中国に比べてぐっと劣ることが推測できる。
富豪が育たなかった理由は、正社員雇用と年功序列賃金体系に第一の原因がある。
戦争で焼け野原になり、食べるものさえなかったときは、全員が平等に食べ物(賃金)を分け合っていた、これが、正社員制度であり、年功序列賃金であり、家賃補助、家族手当である。
たらればの話だが、1970年代に、年功序列賃金を同一労働・同一賃金員に改めるべきだったのだ。ところが、史実は、1970年代に解雇規制法理ができてしまい。そのまま、正社員雇用と年功序列賃金体系が解雇できない契約として解釈されてしまった。社会主義、共産主義思想に毒された当時の裁判官、政治家、企業経営者、そして国民の失敗であった。
正社員の年功序列賃金制度は、共産主義の思想であり、個人の業績を無視して賃金を成果の出ない下の社員の安い給与で固定してしまうのだ、優秀な販売員や発明家に成果に見合った報酬を渡す必要がないという、強欲経営者にとって、魅力的な制度だった。大多数の日本企業は、この雇用慣行を放置してしまった。
「正社員の年功序列賃金制度がよりよい」と頭ごなしに刷り込みされてきた多数の日本人には、自由の国、アメリカはもとより、共産主義の中国の成果別賃金の常識を理解できないかもしれない。
最近、政府は、同一労働・同一賃金員の原則を立法化しようとしているそうだ。より公正には、同一企業・同一地区・同一労働は同一賃金である。
「同一企業・同一地区・同一労働は、同一賃金」は、憲法が保証する法の下での平等の意味をよく考えれば、自然と導かれる結論だ。多くの人は、まだそこまで深く物事を考えていないようだ。誰かが言わないと、気が付かないのかもしれないし、現実と向き会い自分の不正な既得権を失うことが怖いのかも知れない。
公正で合理的であれば、正社員と派遣社員が同一労働をすれば、派遣会社に支払う額が正社員の人件費より高い。もし、正社員の人件費の方が高いというなら、その会社は、正社員にうまく業務を振り分けられていないのだ。その会社は、正社員に賃金に見合った仕事をさせるが、賃下げするか、解雇しなければならないだろう。
富豪が育たなかった理由の第二の原因は、国家による国民の経済的自由の収奪、つまり徴税方法である。
所得税の累進課税は、憲法が保証する法の下での平等を侵し、受益者負担の原則をないがしろにし、経済で活躍しようとする国民の自由を奪う元凶である。
優秀な経営者や発明家に高額の賃金を払えば払うほど、累進課税が足を引っ張る。当然、富豪が少なくなり、新規事業が興らず、社会は停滞する。
累進課税を止めて全員平等な一定の税率が公正で平等である。所得関係の税率(所得税と住民税の合算で考える、預貯金の税率、株式の売買益税率、不動産売買益の税率、法人税についても同様)も個人の所得税と統一することが平等というものだ。
統一税率であれば、優秀な経営者や発明家への報酬を、現金でなく、株式や特許権で支払うことができる。シンプルな同一税率が、平等を促進し、多様な支払い方法(自由度)を可能にし、経済を活性化する。
当然だが、徴税額の上限は、政府の必要最小限までとしなければならない。統一税率を考えると、国際競争上も、所得関係の税率は、20%を超えてはならないことが導かれる。10%が理想であろう。
10%の所得税率で政府を賄えるかという心配は不要だろう。受益者負担の原則を徹底すれば、小さな政府が出来上がる。所得税と不動産税は、原則的に国防、治安維持、防災に使われる。消費税は、自由市場監視だけ使われるからだ。その他の政府事業は、公平で合理的な受益者負担を徹底して、道路は、自動車税とガソリン税、水道は、水道料金、ごみ回収処分は、ごみ袋代、生活保護と老齢年金は、基礎年金、医療費は健康保険でまかなわれることになる。
所得税を支払った後の自由に使える個人の財産を相続や贈与するときに課税することは、二重課税であり、課税理由の合理的意味合いを欠く。共産主義の中国でさえ、相続税がない(定義かあるが課税されていない模様)。相続税がない国がカナダなど、世界にはけっこうある。
相続税と贈与税を廃止すれば、非上場企業の相続で、相続税のために事業を売却、縮小する必要がなくなる。つまり、安心して新規事業を立ち上げて発展させることができるので、国民経済がどんどん発展する可能性が高まる。
消費税は、だれでも一定の税率で平等である。ところが、特定の商品だけ税率を変えるという軽減税率は、憲法が保証する法の下での平等を侵しているのだ。しかも、軽減税率の計算は、国民と税務署の手間まで増やしている悪い行為である。
所得関係の税率を、10%に統一し、相続税と贈与税を廃止し、消費税を8%のままとすれば、世界に開かれた経済的に自由で夢のある日本をアピールできる。これで、世界の富裕層を呼び込み、経済を活性化させる可能性は高まる。
憲法は、9条だけが大切なのではない。「第十三条 すべて国民は、個人として尊重される。生命、自由及び幸福追求に対する国民の権利については、公共の福祉に反しない限り、立法その他の国政の上で、最大の尊重を必要とする。 第十四条 すべて国民は、法の下に平等であつて、人種、信条、性別、社会的身分又は門地により、政治的、経済的又は社会的関係において、差別されない。」の意味を公正に考えないといけない。
社会主義や共産主義では、所得の再配分とか、格差是正という用語を使い累進課税や相続税を主張してくるが、であれば、合理的には、株式の売買での譲渡益にも、累進課税しなければならず、子供達をすべて親から引き離して平等条件で集団生活させることになるが、そんなことをすれば、世界から日本は排除されてしまうだけだろう。社会主義や共産主義のいう、所得の再配分とか、格差是正で、貧者達が富むことは、歴史上一度もなかった。ソ連に代表される共産主義国の歴史を見れば、経済的自由の制限は、国民の平等な没落と権力者の蓄財を意味することがはっきりと分かるし、現在の日本もその危機に飲み込まれつつあると誰でも推測できる。貧者達が富むには、貧者自身が努力するしかない。
[お金以外の方法は見つからない]
もちろん、お金がすべてではない。
でも、お金を無視すると、100%の人間が暴力による権力闘争向かう。歴史上、暴力の否定を実践できた人間は、極めて少ない。私は、釈迦、イエス・キリスト、ガンジーのわずか三人しか知らない。
日本人には、「武士は食わねど高楊枝」などとお金を蔑む、世界から見て風変りな諺がある。
裏を返せば、「武士は問答無用でお前を切り殺して財産を奪う暴力・権力を振るえるから、お金はいらないのだ」という、とても恐ろしい好戦的な発想だ。古い武士道をそのまま現代では使うことはできない、全面的な見直しが必要だ。
現実の人間にとって、暴力的と権力闘争を回避するには、お金を上手く使うしかないのだ。
世界の経済大国のランキングは、
世界の名目GDP 国別ランキング統計・推移(IMF)(2014)
から
| 1 | 米国 | 17,348,075 | |
| 2 | 中国 | 10,356,508 | |
| 3 | 日本 | 4,602,367 | |
| 4 | ドイツ | 3,874,437 | |
| 5 | イギリス | 2,950,039 | |
| 6 | フランス | 2,833,687 | |
| 7 | ブラジル | 2,346,583 | |
| 8 | イタリア | 2,147,744 | |
| 9 | インド | 2,051,228 | |
| 10 | ロシア | 1,860,598 |
世界の資産1100億円(10億ドル)以上の大富豪ランキング(2015)を見れば、
米国 536人
中国 213人
ドイツ 103人
インド 90人
ロシア 88人
イギリス 53人
フランス 47人
韓国 30人
台湾 33人
日本 24人
日本の大富豪が少なすぎる。自由の国アメリカだけでなく、共産主義の不自由の国、中国と比べても一桁少ないのだ。
国家のGDP経済規模から比較して、日本人大富豪の人数が、中国、インド、ロシア、韓国、台湾に及ばないのは、ひどく異常な事である。
Wikiなどを読めば、小金持ち(資産10億円以下)については、日本にもかなりいることはわかる。小金持ちは、日本の大企業のサラリーマン経営者たちに多いようだ。
[富豪が少ない日本の将来]
日本で、借金してまで新規に事業を興すことはできない。その理由は簡単だ。銀行が担保のない人間にお金を貸してくれないからだ。
バブル崩壊前までは、土地神話があり、借金と同額の土地を持っていれば融資してもらえた。土地本位制で、日本経済は、戦争後の焼け野原から驚異的に復興した。
バブル崩壊後は、土地の値段が下がり続けており、土地では担保にならず、銀行は融資できないのだ。
将来が不明確な新規事業の立ち上げは、自腹資金ですることになる。新規事業の初期投資は、最低10億円はかかる。本当の富豪(資産10億円以上)でないと、新規に事業を興すことは難しい。
日本がバブル崩壊(1991年)から停滞して韓国に追いつかれ、中国に抜き去られた本当の理由は、日本には富豪が少ないことに原因がある。
このままでは、日本が発展する速度は遅く、世界からさらに置いてきぼりにされる。
[日本で富豪が育たなかった理由]
富豪が育たなかった理由は、正社員雇用と年功序列賃金体系に第一の原因がある。
戦争で焼け野原になり、食べるものさえなかったときは、全員が平等に食べ物(賃金)を分け合っていた、これが、正社員制度であり、年功序列賃金であり、家賃補助、家族手当である。
たらればの話だが、1970年代に、年功序列賃金を同一労働・同一賃金員に改めるべきだったのだ。ところが、史実は、1970年代に解雇規制法理ができてしまい。そのまま、正社員雇用と年功序列賃金体系が解雇できない契約として解釈されてしまった。社会主義、共産主義思想に毒された当時の裁判官、政治家、企業経営者、そして国民の失敗であった。
正社員の年功序列賃金制度は、共産主義の思想であり、個人の業績を無視して賃金を成果の出ない下の社員の安い給与で固定してしまうのだ、優秀な販売員や発明家に成果に見合った報酬を渡す必要がないという、強欲経営者にとって、魅力的な制度だった。大多数の日本企業は、この雇用慣行を放置してしまった。
「正社員の年功序列賃金制度がよりよい」と頭ごなしに刷り込みされてきた多数の日本人には、自由の国、アメリカはもとより、共産主義の中国の成果別賃金の常識を理解できないかもしれない。
最近、政府は、同一労働・同一賃金員の原則を立法化しようとしているそうだ。より公正には、同一企業・同一地区・同一労働は同一賃金である。
「同一企業・同一地区・同一労働は、同一賃金」は、憲法が保証する法の下での平等の意味をよく考えれば、自然と導かれる結論だ。多くの人は、まだそこまで深く物事を考えていないようだ。誰かが言わないと、気が付かないのかもしれないし、現実と向き会い自分の不正な既得権を失うことが怖いのかも知れない。
公正で合理的であれば、正社員と派遣社員が同一労働をすれば、派遣会社に支払う額が正社員の人件費より高い。もし、正社員の人件費の方が高いというなら、その会社は、正社員にうまく業務を振り分けられていないのだ。その会社は、正社員に賃金に見合った仕事をさせるが、賃下げするか、解雇しなければならないだろう。
富豪が育たなかった理由の第二の原因は、国家による国民の経済的自由の収奪、つまり徴税方法である。
所得税の累進課税は、憲法が保証する法の下での平等を侵し、受益者負担の原則をないがしろにし、経済で活躍しようとする国民の自由を奪う元凶である。
優秀な経営者や発明家に高額の賃金を払えば払うほど、累進課税が足を引っ張る。当然、富豪が少なくなり、新規事業が興らず、社会は停滞する。
累進課税を止めて全員平等な一定の税率が公正で平等である。所得関係の税率(所得税と住民税の合算で考える、預貯金の税率、株式の売買益税率、不動産売買益の税率、法人税についても同様)も個人の所得税と統一することが平等というものだ。
統一税率であれば、優秀な経営者や発明家への報酬を、現金でなく、株式や特許権で支払うことができる。シンプルな同一税率が、平等を促進し、多様な支払い方法(自由度)を可能にし、経済を活性化する。
当然だが、徴税額の上限は、政府の必要最小限までとしなければならない。統一税率を考えると、国際競争上も、所得関係の税率は、20%を超えてはならないことが導かれる。10%が理想であろう。
10%の所得税率で政府を賄えるかという心配は不要だろう。受益者負担の原則を徹底すれば、小さな政府が出来上がる。所得税と不動産税は、原則的に国防、治安維持、防災に使われる。消費税は、自由市場監視だけ使われるからだ。その他の政府事業は、公平で合理的な受益者負担を徹底して、道路は、自動車税とガソリン税、水道は、水道料金、ごみ回収処分は、ごみ袋代、生活保護と老齢年金は、基礎年金、医療費は健康保険でまかなわれることになる。
所得税を支払った後の自由に使える個人の財産を相続や贈与するときに課税することは、二重課税であり、課税理由の合理的意味合いを欠く。共産主義の中国でさえ、相続税がない(定義かあるが課税されていない模様)。相続税がない国がカナダなど、世界にはけっこうある。
相続税と贈与税を廃止すれば、非上場企業の相続で、相続税のために事業を売却、縮小する必要がなくなる。つまり、安心して新規事業を立ち上げて発展させることができるので、国民経済がどんどん発展する可能性が高まる。
消費税は、だれでも一定の税率で平等である。ところが、特定の商品だけ税率を変えるという軽減税率は、憲法が保証する法の下での平等を侵しているのだ。しかも、軽減税率の計算は、国民と税務署の手間まで増やしている悪い行為である。
所得関係の税率を、10%に統一し、相続税と贈与税を廃止し、消費税を8%のままとすれば、世界に開かれた経済的に自由で夢のある日本をアピールできる。これで、世界の富裕層を呼び込み、経済を活性化させる可能性は高まる。
社会主義や共産主義では、所得の再配分とか、格差是正という用語を使い累進課税や相続税を主張してくるが、であれば、合理的には、株式の売買での譲渡益にも、累進課税しなければならず、子供達をすべて親から引き離して平等条件で集団生活させることになるが、そんなことをすれば、世界から日本は排除されてしまうだけだろう。社会主義や共産主義のいう、所得の再配分とか、格差是正で、貧者達が富むことは、歴史上一度もなかった。ソ連に代表される共産主義国の歴史を見れば、経済的自由の制限は、国民の平等な没落と権力者の蓄財を意味することがはっきりと分かるし、現在の日本もその危機に飲み込まれつつあると誰でも推測できる。貧者達が富むには、貧者自身が努力するしかない。
[お金以外の方法は見つからない]
もちろん、お金がすべてではない。
でも、お金を無視すると、100%の人間が暴力による権力闘争向かう。歴史上、暴力の否定を実践できた人間は、極めて少ない。私は、釈迦、イエス・キリスト、ガンジーのわずか三人しか知らない。
日本人には、「武士は食わねど高楊枝」などとお金を蔑む、世界から見て風変りな諺がある。
裏を返せば、「武士は問答無用でお前を切り殺して財産を奪う暴力・権力を振るえるから、お金はいらないのだ」という、とても恐ろしい好戦的な発想だ。古い武士道をそのまま現代では使うことはできない、全面的な見直しが必要だ。
現実の人間にとって、暴力的と権力闘争を回避するには、お金を上手く使うしかないのだ。
Mar 3, 2016
個人番号カードを受け取ってみたのでアドバイス
個人番号カードの受け取りができると、市役所から通知があり受け取りに行ってきました。
通知書の内容が、意味不明で困ってしまいます。
さらに、通知書に同封されている葉書の文字が小さいく、読みにくい。
セキュリティ(安全保障)に一番重要なこと「本人が受け取るときは、暗証番号を市役所の端末で自分で入力するので、通知書に書いてはいけない」が、通知書のどこにも書いてありません。
受け取り窓口でトラブルがあり、もめている市民が大勢いました。
これから受け取りに行く皆さんへのおすすめは、
です。
また、4桁の数字となる三種類の暗証番号は、
通知書の表記名・順序が端末の入力画面の表記名・順序と異なります。
異なる暗証番号を設定される方は、よくよく注意してください。
この画面には、驚きあきれ果てました。
日本政府とその下請け系列の電子情報産業が、
利用者の操作性をいまだに無視していることを痛感します。
かつて自分も所属していた業界だけに、残念でしかたありません。
通知書の内容が、意味不明で困ってしまいます。
さらに、通知書に同封されている葉書の文字が小さいく、読みにくい。
セキュリティ(安全保障)に一番重要なこと「本人が受け取るときは、暗証番号を市役所の端末で自分で入力するので、通知書に書いてはいけない」が、通知書のどこにも書いてありません。
受け取り窓口でトラブルがあり、もめている市民が大勢いました。
これから受け取りに行く皆さんへのおすすめは、
- 市役所からの通知書には自分では何も書ない
- 個人番号と設定したい4種類の暗証番号を別の用紙に控える
- 必要書類持参(先に受領した紙の個人番号カード、自動車運転免許証、印鑑)
- 市役所で説明を聞きながら記入
です。
また、4桁の数字となる三種類の暗証番号は、
通知書の表記名・順序が端末の入力画面の表記名・順序と異なります。
異なる暗証番号を設定される方は、よくよく注意してください。
この画面には、驚きあきれ果てました。
日本政府とその下請け系列の電子情報産業が、
利用者の操作性をいまだに無視していることを痛感します。
かつて自分も所属していた業界だけに、残念でしかたありません。
Mar 2, 2016
ハッシュテーブルのスロット数が素数がよい理由と誕生日のパラドックス
最近、プログラマーがハッシュテーブルを実装する機会は少ない。
現代のプログラミング言語では、ハッシュテーブルはライブラリーに完備されているためだ。
C言語でも、オープンソースを探せば、良いライブラリーが見つかる。
C言語をよく使う自分は、趣味でハッシュテーブルを自作して来た。
最近またハッシュテーブルを自作して、本質を深く理解できたので、メモしておく。
C言語を学び、ハッシュテーブル、リストなどのデータ格納アルゴリズムを一度は実装して確認することで、コンピューターで大量のデータを取り扱う基本を学ぶことができる。
ハッシュテーブルは、データをキーと値の組で保管するものだ。
キーは、数字ではなく、名前のような文字列や、複数の数値の組み合わせである。
値も複雑なデータの組み合わせとなる。
キーはデータを一意に区別できるものである。
複雑なキー情報に一致する値を素早く探し出すために、ハッシュという方法を用いる。
登録されるデータの最大の個数 M をあらかじめ想定しておき、
複雑なキー情報から単純で高速な方法で、0から(M-1)までの数値 Si をハッシュ計算し、
それを、ハッシュテーブルのインデックス番号として利用するのだ。
ハッシュ計算は、データを一意に区別することができる複雑なキーのすべての情報を用いて、
これを log2(M)ビット長に圧縮するためにある。
ハッシュ値は、0から(M-1)までに一様に散らばるように工夫する。
コンピューターの整数計算は、Mをはるかに超える桁数(32bitや64bitで)で行うため、
いったん大きな整数に圧縮してから、 M で割り算した余りを求めて、
0から(M-1)までに収めるのだ。
キーである長い文字列をいったん一つの整数に圧縮する方法で最も楽な方法は、全文字を数値として扱いそれらを合計することである。キーが複数の整数を含む配列でも同様である。
合計法の結果をMで割り算して余りを求めることなるが、Mが2のべき乗(2, 4, 8, 16, 32, ...)の場合は好ましくない。その理由は、コンピューター内部で文字も整数も2進数で表現されているため、合計法の結果の2進数の下位桁は、もともとのキーのそれぞれの2進数の下位桁でのみを合計された物であり、上位桁の情報を一切含まないからである。
従って合計法を用いてハッシュ計算をする場合、Mは、約数に2を含まないほうがよいのだ。ならば、いっそのことMは素数(prime number)がより好ましいとなる。
合計法は簡単で高速であるが、文字列"ABC"と文字列"CBA"が同じ結果になるという欠点を持つ。合計法は、文字の出現順序を圧縮情報に取り込んでいないことが原因だ。文字の出現順序をとりこむためには、合計値を加算する前に、古い合計値のビット列を1ビットだけ回転させるとよいだろう。C言語的には、以下である。
#define BIT_LEN (sizeof(unsigned int) * 8)
unsigned int hash_sum = 0;
for(i = 0; keyText[i] != 0; ++i){
hash_sum = ((hash_sum << 1) | (hash_sum >>(BIT_LEN - 1))) + (unsigned int)keyText[i];
}
slotIndex = hash_sum % primeM;
この hash_sum 値は、キーの付加情報として保存しておいたほうが、テーブルを拡張するときにこれを再計算することが不要になる。
(C言語で高度に汎用化したハッシュテーブルライブラリーを用意するとき、キーの比較関数だけでなく、hash_sumの計算関数をもポインタで渡すようなライブラリーを設計することになる。さらに、キーと値の複写関数や消去解放関数も用意することになるだろう。)
ハッシュテーブルのハッシュ計算はどのような実装をしても、結果値の衝突が必ず発生しうる。
衝突が起きた時に、どうやって格納するかを考えておかなければならない。
M個までしか登録しないという前提があれば、slotIndexを加算して次のスロットに格納するという方法がある。次のスロットが使用中ならさらに加算してそのまた次に格納する、未使用スロットが見つからずどんどん加算してslotIndexがMになったら、0に戻して探すのである。何とか法というらしいが、あまり良い方法とは言えない。理由は、M個までしか登録できないこと。ハッシュ値を計算してslotIndexを求めてもそこにデータがいない可能性があるからである。つまり、衝突の恐れがあるのでデータ読み出しに最大でM回の比較時間がかかるのだ。
M個以上のデータを登録できるようにしたいし、さらに、ハッシュ値を計算してslotIndexを求めたらそこにデータがいることを保証もしたい。そこで、slotIndexの位置に、一方向リストを格納する。リストの要素で、キーと値の組(さらにhash_sum 値も)格納しておくのだ。
実装を間違えないようにしたいことは、一方向リストにデータを追加するときは、リストの最後ではなくリストの先頭につなぐことが、処理時間を少なくできる方法である。
誕生日のパラドックスとは、学校の30人クラスには、誕生日が同じ人がけっこうな確率でいるという事実である。以下の計算を見てほしい。
n人のクラスで誕生日がすべて異なる確率 probability p1 は、
p1(n) = 365! / ( (365 ^ n) * (365 - n)! )
n人のクラスで誕生日が同じ人が2人以上いる確率 p2 は
p2(n) = 1 - p1(n)
n = 23人のとき、確率 p2(23) = 0.507 となる。
もし、 n 人の会社にあなたが入社したら、あなたと同じ誕生日の人がいる確率 p3 は、
p3(n) = 1 - ((365 - 1)/365) ^ n
である。n = 23 ならば、 p3(23) = 0.0611 , p3(253) = 0.5... である。
ハッシュテーブルのサイズをM(素数)とし、すでに n 個のデータが登録されているときに、データを追加登録するとして、すでに同じキーのデータがある確率 p4 は、
p4(M, n) = 1 - ((M - 1)/M) ^ n
この式をnについて解くため、これから、式を変形する。
P = 1 - ((M - 1)/M) ^ n
((M - 1)/M) ^ n = P - 1
n * log((M - 1)/M) = log(P - 1)
n = log(P - 1) / log((M - 1)/M)
P = 0.5として、2のべき乗より少しだけ小さい素数Mについてnを計算してみると
となる。
ハッシュテーブルのサイズをM(素数)とすると、おおよそ70%の使用度になったら、平均的な衝突確率が50%を超えると言えるだろう。
(2のべき乗より少しだけ小さい素数Mとした理由は、ハッシュテーブル領域を動的に確保するとき、確保したいサイズが1024バイト(2^10)の整数倍を超えない範囲でできるだけ大きいほうが、のメモリ利用効率が良いから。2のべき乗より少しだけ大きい素数とすれば、動的に確保したときメモリーで未使用の断片が生まれやすいと言える。)
したがって、ハッシュテーブルのサイズをM(素数)として、テーブルへの登録キーの数が70%を超えたら、テーブルサイズを次の2倍のサイズに拡大する(Mをもっと大きな素数にする)ことが好ましい。
テーブルサイズを拡大するときに、キー、値の組とともに保存しておいた hash_sum 値 を新しい大きなMで割った余りを求めて、新しいスロット番号とすることになる。
高校程度の数学(素数、2進数、確率、べき乗、階乗、対数)、プログラミング言語Cなどの知識が、こういうところで役立っていると言える。
現代のプログラミング言語では、ハッシュテーブルはライブラリーに完備されているためだ。
C言語でも、オープンソースを探せば、良いライブラリーが見つかる。
C言語をよく使う自分は、趣味でハッシュテーブルを自作して来た。
最近またハッシュテーブルを自作して、本質を深く理解できたので、メモしておく。
C言語を学び、ハッシュテーブル、リストなどのデータ格納アルゴリズムを一度は実装して確認することで、コンピューターで大量のデータを取り扱う基本を学ぶことができる。
ハッシュテーブルは、データをキーと値の組で保管するものだ。
キーは、数字ではなく、名前のような文字列や、複数の数値の組み合わせである。
値も複雑なデータの組み合わせとなる。
キーはデータを一意に区別できるものである。
複雑なキー情報に一致する値を素早く探し出すために、ハッシュという方法を用いる。
登録されるデータの最大の個数 M をあらかじめ想定しておき、
複雑なキー情報から単純で高速な方法で、0から(M-1)までの数値 Si をハッシュ計算し、
それを、ハッシュテーブルのインデックス番号として利用するのだ。
ハッシュ計算は、データを一意に区別することができる複雑なキーのすべての情報を用いて、
これを log2(M)ビット長に圧縮するためにある。
ハッシュ値は、0から(M-1)までに一様に散らばるように工夫する。
コンピューターの整数計算は、Mをはるかに超える桁数(32bitや64bitで)で行うため、
いったん大きな整数に圧縮してから、 M で割り算した余りを求めて、
0から(M-1)までに収めるのだ。
キーである長い文字列をいったん一つの整数に圧縮する方法で最も楽な方法は、全文字を数値として扱いそれらを合計することである。キーが複数の整数を含む配列でも同様である。
合計法の結果をMで割り算して余りを求めることなるが、Mが2のべき乗(2, 4, 8, 16, 32, ...)の場合は好ましくない。その理由は、コンピューター内部で文字も整数も2進数で表現されているため、合計法の結果の2進数の下位桁は、もともとのキーのそれぞれの2進数の下位桁でのみを合計された物であり、上位桁の情報を一切含まないからである。
従って合計法を用いてハッシュ計算をする場合、Mは、約数に2を含まないほうがよいのだ。ならば、いっそのことMは素数(prime number)がより好ましいとなる。
合計法は簡単で高速であるが、文字列"ABC"と文字列"CBA"が同じ結果になるという欠点を持つ。合計法は、文字の出現順序を圧縮情報に取り込んでいないことが原因だ。文字の出現順序をとりこむためには、合計値を加算する前に、古い合計値のビット列を1ビットだけ回転させるとよいだろう。C言語的には、以下である。
#define BIT_LEN (sizeof(unsigned int) * 8)
unsigned int hash_sum = 0;
for(i = 0; keyText[i] != 0; ++i){
hash_sum = ((hash_sum << 1) | (hash_sum >>(BIT_LEN - 1))) + (unsigned int)keyText[i];
}
slotIndex = hash_sum % primeM;
この hash_sum 値は、キーの付加情報として保存しておいたほうが、テーブルを拡張するときにこれを再計算することが不要になる。
(C言語で高度に汎用化したハッシュテーブルライブラリーを用意するとき、キーの比較関数だけでなく、hash_sumの計算関数をもポインタで渡すようなライブラリーを設計することになる。さらに、キーと値の複写関数や消去解放関数も用意することになるだろう。)
ハッシュテーブルのハッシュ計算はどのような実装をしても、結果値の衝突が必ず発生しうる。
衝突が起きた時に、どうやって格納するかを考えておかなければならない。
M個までしか登録しないという前提があれば、slotIndexを加算して次のスロットに格納するという方法がある。次のスロットが使用中ならさらに加算してそのまた次に格納する、未使用スロットが見つからずどんどん加算してslotIndexがMになったら、0に戻して探すのである。何とか法というらしいが、あまり良い方法とは言えない。理由は、M個までしか登録できないこと。ハッシュ値を計算してslotIndexを求めてもそこにデータがいない可能性があるからである。つまり、衝突の恐れがあるのでデータ読み出しに最大でM回の比較時間がかかるのだ。
M個以上のデータを登録できるようにしたいし、さらに、ハッシュ値を計算してslotIndexを求めたらそこにデータがいることを保証もしたい。そこで、slotIndexの位置に、一方向リストを格納する。リストの要素で、キーと値の組(さらにhash_sum 値も)格納しておくのだ。
実装を間違えないようにしたいことは、一方向リストにデータを追加するときは、リストの最後ではなくリストの先頭につなぐことが、処理時間を少なくできる方法である。
誕生日のパラドックスとは、学校の30人クラスには、誕生日が同じ人がけっこうな確率でいるという事実である。以下の計算を見てほしい。
n人のクラスで誕生日がすべて異なる確率 probability p1 は、
p1(n) = 365! / ( (365 ^ n) * (365 - n)! )
n人のクラスで誕生日が同じ人が2人以上いる確率 p2 は
p2(n) = 1 - p1(n)
n = 23人のとき、確率 p2(23) = 0.507 となる。
もし、 n 人の会社にあなたが入社したら、あなたと同じ誕生日の人がいる確率 p3 は、
p3(n) = 1 - ((365 - 1)/365) ^ n
である。n = 23 ならば、 p3(23) = 0.0611 , p3(253) = 0.5... である。
ハッシュテーブルのサイズをM(素数)とし、すでに n 個のデータが登録されているときに、データを追加登録するとして、すでに同じキーのデータがある確率 p4 は、
p4(M, n) = 1 - ((M - 1)/M) ^ n
この式をnについて解くため、これから、式を変形する。
P = 1 - ((M - 1)/M) ^ n
((M - 1)/M) ^ n = P - 1
n * log((M - 1)/M) = log(P - 1)
n = log(P - 1) / log((M - 1)/M)
P = 0.5として、2のべき乗より少しだけ小さい素数Mについてnを計算してみると
| index | べき乗 | 素数M | n | (n/素数M) |
| 1 | 2 | 2 | 1.00 | 0.50 |
| 2 | 4 | 3 | 1.71 | 0.57 |
| 3 | 8 | 7 | 4.50 | 0.64 |
| 4 | 16 | 13 | 8.66 | 0.67 |
| 5 | 32 | 31 | 21.14 | 0.68 |
| 6 | 64 | 61 | 41.93 | 0.69 |
| 7 | 128 | 127 | 87.68 | 0.69 |
| 8 | 256 | 251 | 173.63 | 0.69 |
| 9 | 512 | 509 | 352.47 | 0.69 |
| 10 | 1,024 | 1,021 | 707.36 | 0.69 |
| 11 | 2,048 | 2,039 | 1,412.98 | 0.69 |
| 12 | 4,096 | 4,093 | 2,836.70 | 0.69 |
| 13 | 8,192 | 8,191 | 5,677.22 | 0.69 |
| 14 | 16,384 | 16,381 | 11,354.10 | 0.69 |
| 15 | 32,768 | 32,749 | 22,699.53 | 0.69 |
| 16 | 65,536 | 65,521 | 45,415.35 | 0.69 |
ハッシュテーブルのサイズをM(素数)とすると、おおよそ70%の使用度になったら、平均的な衝突確率が50%を超えると言えるだろう。
(2のべき乗より少しだけ小さい素数Mとした理由は、ハッシュテーブル領域を動的に確保するとき、確保したいサイズが1024バイト(2^10)の整数倍を超えない範囲でできるだけ大きいほうが、のメモリ利用効率が良いから。2のべき乗より少しだけ大きい素数とすれば、動的に確保したときメモリーで未使用の断片が生まれやすいと言える。)
したがって、ハッシュテーブルのサイズをM(素数)として、テーブルへの登録キーの数が70%を超えたら、テーブルサイズを次の2倍のサイズに拡大する(Mをもっと大きな素数にする)ことが好ましい。
テーブルサイズを拡大するときに、キー、値の組とともに保存しておいた hash_sum 値 を新しい大きなMで割った余りを求めて、新しいスロット番号とすることになる。
高校程度の数学(素数、2進数、確率、べき乗、階乗、対数)、プログラミング言語Cなどの知識が、こういうところで役立っていると言える。
Feb 19, 2016
ささいな話
とるにたらないささいな話です。
読めない漢字が時々あります。
「些細」
「ささい」と読むそうです。
関連して、
「些細」(ささい)[わずか。取るに足らない事。「瑣細」とも書く]
「仔細」(しさい)[物事のくわしい事情、「仔細ない」は差し支えないの意味、「子細」とも書く]「委細」(いさい)[くわしいこと。こまごました事情、例「委細面談」]
漢字
「些」([音]サ、シャ、[訓]いささか)[いささか。わずか。些少(さしょう)]
「此」([音]シ、[訓]ここ、この)[この、これ、ここの意味、「彼此(かし)」あれこれの意味、「此方(こっち、こなた、こちら)」]
「瑣」([音]サ)[ちいさい、細かい。くだくだしい、わずらわしい、煩瑣(はんさ)。くさり。]
「細」([音]、[訓])[]
「仔」([音]シ)[こまかい、詳しい。虫や魚の子。]
「委」([音]イ、[訓]ゆだねる、くわしい)[女がからだをくねくねさせるの意味から任せるに変わった。委(ゆだ)ねる。まかせる。詳しい、委細(いさい)。捨てる、委棄(いき)]
読めない漢字が時々あります。
「些細」
「ささい」と読むそうです。
関連して、
「些細」(ささい)[わずか。取るに足らない事。「瑣細」とも書く]
「仔細」(しさい)[物事のくわしい事情、「仔細ない」は差し支えないの意味、「子細」とも書く]「委細」(いさい)[くわしいこと。こまごました事情、例「委細面談」]
漢字
「些」([音]サ、シャ、[訓]いささか)[いささか。わずか。些少(さしょう)]
「此」([音]シ、[訓]ここ、この)[この、これ、ここの意味、「彼此(かし)」あれこれの意味、「此方(こっち、こなた、こちら)」]
「瑣」([音]サ)[ちいさい、細かい。くだくだしい、わずらわしい、煩瑣(はんさ)。くさり。]
「細」([音]、[訓])[]
「仔」([音]シ)[こまかい、詳しい。虫や魚の子。]
「委」([音]イ、[訓]ゆだねる、くわしい)[女がからだをくねくねさせるの意味から任せるに変わった。委(ゆだ)ねる。まかせる。詳しい、委細(いさい)。捨てる、委棄(いき)]
Subscribe to:
Posts (Atom)