「ETCで料金踏み倒しが増加中」記事へのコメント

14万枚

[nobuo (263)]

私もこの記事を読んだときに、不正カードのデータを貯めておくのは14万枚しかないの？と疑問に思いました。これを増やすことって、難しいんですかね？単純にストレージを増やせばいいだけということはないのでしょうか？

ETC

--
nobuo * Who's gonna die first? *

リアルタイム処理・・・

[kicchy (4711)]

>私もこの記事を読んだときに、不正カードのデータを貯めておくのは14万枚しかないの？と疑問に思いました。
>これを増やすことって、難しいんですかね？単純にストレージを増やせばいいだけということはないのでしょうか？

ETCの場合、検索時間が一定以内でないとダメということも考えないといけないのでは？
# データが増

Re:リアルタイム処理・・・

[Ryo.F (3896)]

> データが増えると検索時間はかかるし、

この場合に限って言えば、データが増えても検索時間がO(1)で済むアルゴリズムがありますよね。最もトリビアルには、カード番号を添字とする配列にOK・NGを入れておけばよいし、カード番号が飛んでいると考えても、トライを使えば、一つのカード番号の桁数をkとして、検索時間はO(k)、kは定数なので、O(1)ですね。
必要とする記憶領域は、不正カードの数をnとするとk*nに比例します。つまり、O(n)。単純に考えて、メモリのアドレス長を4byte、カード番号を16桁、不正カードを最大一千万枚扱うと考えても、6.4Gbytesもメモリがあれば、メモリ上だけで検索できます。
他にもハッシュで実現すると言う方法もありますね。

＃富豪的プログラミングだ(笑)。

Re:リアルタイム処理・・・

[Anonymous Coward]

メモリのアドレス長を4byte、カード番号を16桁、不正カードを最大一千万枚扱うと考えても、6.4Gbytesもメモリがあれば、メモリ上だけで検索できます。

くだらんアルゴリズムより、アドレスが4byteで表現できる6.4Gbyteの主記憶の方が実に興味をそそりますな。

Re:リアルタイム処理・・・

[Ryo.F (3896)]

4byte=1wordとして、byte単位でなく、word単位にアドレスを割当てるマシンであれば、ぎりぎり足りますね。そんなに興味深いもんでもないですよ(笑)。

いや、正直言って見落としてました。ご指摘ありがとう。

Re:リアルタイム処理・・・

[Anonymous Coward]

確かに「メモリのアドレス」というのは正しくないですが、アドレスバス64bitでリニアに領域が取れれば

char CardNum[10000000][16];

としてやればインデックスはint32で足りますね。