อัลกอริทึมใหม่สำหรับนับจำนวนรายการที่ไม่ซ้ำอย่างมีประสิทธิภาพ

 (quantamagazine.org)
2 คะแนน โดย GN⁺ 2024-05-17 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • อัลกอริทึม CVM ใช้ประมาณค่า จำนวนรายการที่แตกต่างกัน ในสตรีมข้อมูลขนาดยาว ทำให้สามารถประเมินจำนวนรายการไม่ซ้ำได้โดยไม่ต้องเก็บรายการทั้งหมด
  • มุ่งเน้นที่ ปัญหาการหาจำนวนสมาชิกไม่ซ้ำ (distinct elements problem) เมื่อข้อมูลนำเข้าทั้งหมดมีขนาดเกินหน่วยความจำ และสามารถนำไปใช้กับล็อกขนาดใหญ่หรือสตรีมเหตุการณ์ที่มีข้อมูลซ้ำจำนวนมากได้
  • เก็บไว้เพียงบางรายการในหน่วยความจำที่จำกัด และทุกครั้งที่พื้นที่เต็มจะทำ การลบแบบสุ่ม ซ้ำ ๆ เพื่อให้ความน่าจะเป็นที่แต่ละรายการจะเหลืออยู่มีความเท่ากัน
  • ในตัวอย่าง Hamlet เมื่อใช้หน่วยความจำ 100 คำและทดลอง 5 ครั้ง ได้ค่าเฉลี่ยประมาณ 3,955 ใกล้เคียงกับจำนวนคำไม่ซ้ำจริงที่ 3,967 คำ และเมื่อใช้หน่วยความจำ 1,000 คำ ค่าเฉลี่ยดีขึ้นเป็น 3,964
  • ยิ่งหน่วยความจำมาก ความแม่นยำก็ยิ่งสูง และหากมีมากพอจะเก็บรายการไม่ซ้ำทั้งหมดได้ ก็อาจได้ ความแม่นยำ 100%

การนับรายการที่ไม่ซ้ำในสตรีมข้อมูลขนาดยาว

  • เป้าหมายคือการประมาณ จำนวนรายการไม่ซ้ำหลังตัดรายการซ้ำออก อย่างมีประสิทธิภาพจากรายการยาวที่มีข้อมูลไหลเข้ามาทีละรายการ
  • วิธีที่ง่ายที่สุดคือเก็บทุกรายการที่เคยเห็นไว้ทั้งหมด และทุกครั้งที่มีรายการใหม่เข้ามาก็นำไปเทียบกับรายการเดิม
    • ในการสำรวจสัตว์ป่า ต้องคอยตรวจสอบรายชื่อภาพสัตว์ที่เคยเห็นแล้วอยู่ตลอด
    • หากรายการมีขนาดระดับหลายพันล้าน เช่น จำนวนผู้ใช้ที่ล็อกอินรายวันของ Facebook การจัดเก็บและเปรียบเทียบจะทำได้ยาก
  • CVM เป็นอัลกอริทึมที่ตั้งชื่อตาม Sourav Chakraborty, Vinodchandran Variyam และ Kuldeep Meel
  • ใช้ได้กับ รายการที่ข้อมูลเข้ามาเป็นลำดับต่อเนื่อง เช่น คำพูด สินค้าบนสายพานลำเลียง หรือรถยนต์บนทางหลวง

แนวคิดหลักของอัลกอริทึม CVM

  • CVM ไม่ได้เก็บทุกรายการ แต่เก็บเฉพาะบางรายการที่พอใส่ในหน่วยความจำที่มีจำกัด
  • ใช้ ความสุ่ม เพื่อควบคุมความน่าจะเป็นที่แต่ละรายการไม่ซ้ำจะคงอยู่ในรายการสุดท้าย
  • Andrew McGregor มองว่าอัลกอริทึมนี้เรียบง่ายมากและนำไปใช้งานได้ง่าย จนอาจกลายเป็นแนวทางพื้นฐานสำหรับปัญหาการหาจำนวนสมาชิกไม่ซ้ำในโลกจริง

วิธีทำงานผ่านตัวอย่าง Hamlet

  • Hamlet มีคำทั้งหมด 30,557 คำ และอัลกอริทึมนี้ใช้เพื่อประมาณ จำนวนคำที่ไม่ซ้ำ
  • สมมติว่าหน่วยความจำเป็นไวต์บอร์ดที่จุได้ 100 คำ ช่วงแรกจะข้ามคำซ้ำและเขียนคำไม่ซ้ำ 100 คำแรกลงไป
  • เมื่อพื้นที่เต็ม จะโยนเหรียญให้แต่ละคำ
    • ถ้าออกหัว จะเก็บคำนั้นไว้
    • ถ้าออกก้อย จะลบคำนั้นออก
    • หลังขั้นเตรียมการนี้ จะเหลือคำไม่ซ้ำอยู่ราว 50 คำ

เงื่อนไขการคงอยู่ที่เข้มงวดขึ้นในแต่ละรอบ

  • ในรอบ 1 จะเติมคำใหม่ต่อไป และถ้าคำที่มีอยู่ในรายการปรากฏขึ้นอีกครั้ง ก็จะโยนเหรียญและลบออกหากออกก้อย
  • เมื่อรายการเต็ม 100 คำอีกครั้ง จะลบออกประมาณครึ่งหนึ่งตามผลการโยนเหรียญ 100 ครั้ง และจบรอบ 1
  • ตั้งแต่รอบ 2 เป็นต้นไป คำแต่ละคำจะอยู่รอดได้ยากขึ้น
    • เมื่อมีคำซ้ำปรากฏขึ้น จะลบออกหากออกก้อย
    • หากออกหัว จะโยนเหรียญอีกครั้ง และจะเก็บไว้ต่อเมื่อครั้งที่สองออกหัวด้วย
  • ในรอบที่สาม ต้องออกหัวติดกัน 3 ครั้ง และในรอบที่สี่ต้องออกหัวติดกัน 4 ครั้ง
  • โดยทั่วไป เมื่อจบ รอบที่ k ความน่าจะเป็นที่แต่ละคำจะยังเหลืออยู่จะเท่ากับ 1/2^k

การคำนวณค่าประมาณและผลการทดลอง

  • นำจำนวนคำที่เหลืออยู่ในรายการสุดท้ายไปหารด้วยความน่าจะเป็นที่จะยังเหลืออยู่ ก็จะได้ค่าประมาณของจำนวนคำไม่ซ้ำทั้งหมด
  • ตัวอย่างเช่น หากหลังผ่าน 6 รอบเหลือ 61 คำ ก็หารด้วยความน่าจะเป็น 1/2^6 เพื่อได้ค่าประมาณ 3,904
  • จำนวนคำไม่ซ้ำจริงใน Hamlet คือ 3,967 คำ
  • ยิ่งขนาดหน่วยความจำใหญ่ขึ้น ค่าประมาณก็ยิ่งเข้าใกล้ค่าจริง
    • เมื่อใช้หน่วยความจำ 100 คำและรัน 5 ครั้ง ค่าประมาณเฉลี่ยคือ 3,955
    • เมื่อใช้หน่วยความจำ 1,000 คำ ค่าประมาณเฉลี่ยคือ 3,964
  • Variyam และเพื่อนร่วมงานได้พิสูจน์ทางคณิตศาสตร์ว่า ความแม่นยำของเทคนิคนี้ขยายตาม ขนาดหน่วยความจำ

วิธีแก้ที่เรียบง่ายแต่ไม่ธรรมดา

  • CVM ถูกมองว่าเป็นความก้าวหน้าสำคัญของ ปัญหาการหาจำนวนสมาชิกไม่ซ้ำ ซึ่งมีการศึกษามานานกว่า 40 ปี
  • William Kuszmaul มองว่า แม้แต่ปัญหาพื้นฐานมากและถูกศึกษาอย่างกว้างขวางแล้ว ก็ยังอาจมีวิธีแก้ที่เรียบง่ายแต่ไม่ใช่สิ่งที่ใครจะนึกออกได้ง่าย ๆ หลงเหลืออยู่

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-05-17
ความคิดเห็นบน Hacker News

  • เคยร่วมกับผู้เขียนในการทำ implementation เวอร์ชัน การนับปริมาตร DNF ของอัลกอริทึมนี้ บทความที่เกี่ยวข้องอยู่ที่นี่: https://www.msoos.org/2023/09/pepin-our-probabilistic-approx...
    โค้ดอยู่ที่นี่: https://github.com/meelgroup/pepin
    อัลกอริทึมนี้เร็วอย่างเหลือเชื่อ จนบางครั้ง 30% ของเวลาทั้งหมดหมดไปกับ I/O สำหรับอ่านไฟล์เลยทีเดียว อนึ่ง Knuth ก็มีส่วนร่วมกับอัลกอริทึมนี้ด้วย และโน้ตของเขาอยู่ที่นี่: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
    เขาหยุดงาน TAOCP ไปทั้งเดือนเพื่อมาทำสิ่งนี้ และก็ยอดเยี่ยมจนน่าเหลือเชื่ออย่างที่คุณนึกภาพไว้นั่นแหละ

    • น่าสนใจมาก และผมสนใจคนที่มีพรสวรรค์โดดเด่นเป็นพิเศษมาก อยากรู้ว่าทำไมถึงรู้สึกว่า Knuth ยอดเยี่ยมขนาดนั้น มีช่วงเวลาพิเศษอะไรไหม เป็นความเร็วในการเข้าใจไอเดีย หรือเป็นความสามารถในการอธิบายให้ง่ายกันแน่
    • นี่ดูโง่นะ โง่มาก ๆ แต่ผมพลาดอะไรไปหรือเปล่า? นี่ไม่ใช่การนับ แต่เป็นแค่ การสุ่มตัวอย่าง และถ้าต้องการนับคำที่แตกต่างกันทั้งหมดจริง ๆ ดูเหมือนว่าการใช้หน่วยความจำจะไม่ต่างจากการนับแบบตรง ๆ เลย
    • คุณอาจจะรู้อยู่แล้วก็ได้ แต่ผมสงสัยว่าทำไมไม่ใช้วิธีเรียงลำดับให้ count ที่ใหญ่กว่าอยู่ก่อน แล้วเมื่อเต็มก็ทิ้งครึ่งล่างไป เหตุผลอาจ obvious สำหรับคนอื่น แต่ผมอยากรู้
    • สงสัยว่า use case หลักของอัลกอริทึมนี้คืออะไร
    • ทีนี้ก็มีคนให้โทษแล้วว่าเป็นเหตุให้หนังสือเล่มถัดไปของ Knuth ออกช้า :)

  • อัลกอริทึมนี้ดูคล้ายกับ HyperLogLog ที่ถูกอ้างถึงใน paper ด้วย ใช้ insight แบบเดียวกันคือดูว่าหน้า/ก้อยออกต่อเนื่องกันหรือไม่เพื่อให้ได้ค่าประมาณ แต่เหมือนพลิกไอเดียกลับด้าน ทำให้เป็นอัลกอริทึมที่ง่ายกว่า โดยทิ้งค่าที่จำไว้ตามความต่อเนื่องของผลการโยนเหรียญ
    มันทำงานได้มีประสิทธิภาพเป็นพิเศษในสถานการณ์แบบ streaming ทำให้สามารถคงสิ่งที่คล้าย “counter” สำหรับนับจำนวน element ที่แตกต่างกันไว้ได้ แม้จะมีอัตราความคลาดเคลื่อน
    ข้อดีของ HyperLogLog คือในแง่หนึ่งมันทำงานคล้าย hash set คุณสามารถเพิ่มรายการ นับจำนวนรายการที่แตกต่างกัน และที่สำคัญคือ merge HLL สองตัวเพื่อสร้าง union ได้ ขณะเดียวกันหน่วยความจำก็คงที่เพียงไม่กี่ KB แม้กับชุดข้อมูลหลายพันล้านรายการ data store แบบ distributed ใช้เทคนิคนี้ใน cardinality agg ของ Elasticsearch/OpenSearch และ PFADD/PFMERGE/PFCOUNT ของ Redis/Redict
    ไม่แน่ใจว่าอัลกอริทึม CVM เปรียบเทียบกับ HLL อย่างไรอย่างละเอียด แต่ในเมื่อได้ให้ Knuth review แล้ว และนักศึกษาปริญญาตรีก็ implement ได้ง่าย ก็น่าจะเป็นอัลกอริทึมที่ค่อนข้างดี

    • HLL สามารถประมาณได้ทั้ง union และ intersection ของ HLL สองตัว จึงใช้ในการประมาณ cardinality ของ join ได้ด้วย
      http://oertl.github.io/hyperloglog-sketch-estimation-paper/
    • data structure เหล่านี้ก็ merge ได้เช่นกัน ถ้า “round” ของ instance สองตัวที่จะ merge ไม่เท่ากัน ก็ให้ตัวที่อยู่ใน round ก่อนหน้าถูกเลื่อนไปข้างหน้าเท่ากับส่วนต่างของ round กล่าวคือสุ่มทิ้งครึ่งหนึ่ง จากนั้นใส่ค่าจาก list หนึ่งเข้าไปในอีก list แล้ว ignore ค่าซ้ำ ถ้าผลลัพธ์ใหญ่เกินไป ก็สุ่มทิ้งครึ่งหนึ่งแล้วเพิ่มหมายเลข round
      ที่งานก่อนหน้านี้ ผมเคย implement อัลกอริทึมนี้พอดี โดยเก็บค่าประมาณของจำนวนครั้งที่ค่านั้นปรากฏไว้ข้าง ๆ แต่ละค่าด้วย จึงทำให้สร้างรายชื่อโดยประมาณของค่าที่พบบ่อยที่สุดพร้อม count โดยประมาณของแต่ละค่าได้
    • ลองขุดความทรงจำสมัยเรียนเมื่อนานมาแล้ว เลยสงสัยว่า HLL กับ CVM ที่พูดถึงตรงนี้เกี่ยวข้องกับ reservoir sampling ที่เคยเรียนมาอย่างไร?
      สมัยทำงานที่โรงพยาบาล ผมเคยใช้ reservoir sampling เพื่อสร้าง subset เล็ก ๆ ของ record ที่เก็บอยู่ในเทป DAT

  • ใช้เวลาอ่านบทความวิจัยแทบจะพอ ๆ กับอ่านบล็อกโพสต์ และบทความวิจัยมีประโยชน์กว่า
    https://arxiv.org/pdf/2301.10191
    เป็นเรื่องการประมาณคาร์ดินัลลิตีของเซตขององค์ประกอบที่ออกมาจากสตรีม อัลกอริทึมเรียบง่ายมากจนระหว่างอ่านบทความวิจัยก็สามารถลองเขียนโค้ดเล่นเองไปด้วยได้
    ผู้เขียนระบุชัดเจนว่ากลุ่มผู้อ่านและวัตถุประสงค์ของอัลกอริทึมนี้คือ นักศึกษาปริญญาตรีและตำราเรียน

    • คำบรรยายรองของบทความวิจัย “An Algorithm for the (Text) Book” ดูเหมือนจะอ้างถึงคำพูดโด่งดังของ Paul Erdős ที่ว่าเป็นบทพิสูจน์ซึ่ง “มาจาก The Book” เพราะความเรียบง่ายและความงดงามนั้นสง่างามมาก
      Knuth ตรวจทานเอง ดังนั้นเขาอาจประเมินว่าอัลกอริทึมนี้เป็นประเภทนั้นก็ได้ ถ้าเป็นอย่างนั้น สิ่งที่ผู้เขียนใส่ไว้ในชื่อเรื่องอาจดูเหมือนการอวดที่ไม่ถ่อมตัว แต่ก็เป็นเรื่องที่อวดได้เต็มที่
      เดิมทีจำได้ว่าวลีนี้เป็นของ Knuth แต่ความจำผมผิด
    • บล็อกโพสต์มี padding เกินครึ่ง การที่อัลกอริทึมเรียบง่ายเกินกว่าจะเขียนเป็นบล็อกโพสต์ยาว ๆ ได้ก็ถือเป็นเรื่องดี
    • เห็นด้วยว่าบทความวิจัยดีกว่าบล็อกโพสต์ แต่ข้อวิจารณ์อย่างหนึ่งต่อบทความ CVM คือมันมี เงื่อนไขการสิ้นสุด โน้ต CVM ของ Knuth ที่อยู่ในอีกเธรดหนึ่งใช้เพียงลูปเพื่อให้เกิดพื้นที่เพิ่มขึ้นในขั้นตอนลดครึ่ง reservoir
      ดูเหมือนว่าการใช้ลูปธรรมดาจะยุ่งยากน้อยกว่าการอธิบาย https://en.wikipedia.org/wiki/Up_tack [1]
      [1] https://news.ycombinator.com/item?id=40388878
    • เคยเรียนวิทยาการคอมพิวเตอร์มาก่อน แต่ไม่รู้ว่าเพราะสมองเริ่มเรียบเนียนไปแล้วหรือเปล่า อันนี้ดูชวนสับสนเกินจำเป็น
      อย่างแรก การจัดการ contradiction ดูเหมือนเป็นแค่ error หรือ panic แต่ไม่เข้าใจว่าทำไมถึงอธิบายแบบนั้น อีกอย่างสมมติฐาน 1..m ก็ชวนสับสน ไม่แน่ใจว่าต้องรู้ขนาดล่วงหน้าหรือไม่ แต่ดูต่อไปแล้วเหมือนจะไม่ต้องรู้ มีการเลือก threshold และความน่าจะเป็นเปลี่ยนตามขนาดสตรีม แต่คำอธิบายอัลกอริทึมกลับเหมือนว่ามี output เดียว เลยยิ่งสับสน
      Chernoff bound กับ delta/epsilon ก็ไม่ได้อธิบายในบทความวิจัยเลย ทำให้สับสนยิ่งขึ้น โค้ดที่ลอง implement ด้วย Go อยู่ที่นี่: https://github.com/betamos/distinct
      การแยกส่วนที่เกี่ยวกับ threshold ออกไปเป็น helper สมเหตุสมผลกว่าการเผลอ allocate หน่วยความจำมากเกินไปมาก น่าจะต้องมี method สำหรับประมาณความเชื่อมั่นหรืออัตราความผิดพลาดด้วย ไม่มีใครรู้ขนาดสตรีมล่วงหน้า ดังนั้นการอัปเดตค่านี้ระหว่างประมวลผลจึงเป็นธรรมชาติกว่า
    • ถ้าคำว่า “สำหรับนักศึกษาปริญญาตรีและตำราเรียน” ไม่ได้หมายความว่ามันเรียบง่ายพอให้พวกเขาใช้ แต่หมายความว่ามันมีประโยชน์จริง ๆ แค่ในบริบทนั้น ก็อยากให้ช่วยอธิบายว่าทำไมจึงไม่มีประโยชน์สำหรับผู้เชี่ยวชาญ แต่มีประโยชน์เฉพาะกับนักศึกษาปริญญาตรี

  • เมื่อคิดถึงหัวข้อของบทความวิจัย เชิงอรรถนั้นมีเสน่ห์เป็นพิเศษ
    ผู้เขียนบอกว่าแทนที่จะใช้ธรรมเนียมเก่าแก่ในการเรียงชื่อผู้เขียนตามลำดับตัวอักษร พวกเขาเลือกใช้ลำดับแบบสุ่ม และทำเครื่องหมายด้วย r⃝ บันทึกการสุ่มที่ตรวจสอบได้แบบสาธารณะอยู่ที่นี่: https://www.aeaweb.org/journals/policies/random-author-order...
    [0]: https://arxiv.org/pdf/2301.10191

  • คำอธิบายอัลกอริทึมน่าจะผิดหรือเปล่า?
    ถ้า implement “ตรวจสอบว่าอยู่ในรายการแล้วค่อยลบ” ตามคำอธิบายว่า “เมื่อเจอคำที่มีอยู่แล้วในรายการ ให้โยนเหรียญอีกครั้ง และถ้าออกก้อยให้ลบคำนั้น” จะวนซ้ำประมาณ 20 รอบและได้ค่าประมาณมั่ว ๆ อย่าง 772800512
    แต่ถ้าบันทึกคำก่อนแล้วค่อยลบคำเดียวกัน จะได้ 7240 ซึ่งใกล้กับจำนวนคำไม่ซ้ำจริง 7233 กล่าวคือ ลำดับในคำอธิบายสำคัญ แต่ดูเหมือนถูกถ่ายทอดผิด

    • เจอปัญหาเดียวกัน ถ้า implement โดยดูแค่คำอธิบายใน Quanta Magazine โดยไม่ดูบทความ arxiv จะได้ค่าประมาณแบบ 461746372167462146216468796214962164 เสมอ
      หลังจากอ่านบทความวิจัยแล้วจึงได้ค่าประมาณที่ถูกต้อง และปัญหาคือ else ตัวเล็ก ๆ ตัวเดียว คำอธิบายของ Quanta อ่านแล้วเหมือนว่า “ถ้าไม่อยู่ในรายการให้เพิ่ม ไม่เช่นนั้นให้ลบตามความน่าจะเป็น” แต่ implementation ที่ถูกต้องต้องใช้เงื่อนไขความน่าจะเป็นตามหลังโดยไม่ขึ้นกับว่าได้เพิ่มหรือไม่
    • เพิ่งลองแก้โจทย์นี้ แล้วแวะมาดูว่ามีคนอื่นเจอปัญหาเดียวกันไหม ซึ่งก็ใช่ ถ้าทำตามคำอธิบายจะผิด ต้อง implement เป็นเพิ่มค่าใหม่ในแต่ละรอบก่อน แล้ว prune แบบสุ่มตามความน่าจะเป็น และเมื่อหน่วยความจำชนขีดจำกัด ก็ลบครึ่งหนึ่งแบบสุ่มจากทั้งเซต

  • การ ประมาณ จำนวนองค์ประกอบไม่ซ้ำของเซต กับการ นับ จำนวนองค์ประกอบไม่ซ้ำของเซต เป็นคนละเรื่องกันมาก วิธีนี้เจ๋ง แต่ชื่อเรื่องไม่ค่อยดี

    • สองอย่างนี้ไม่ได้ต่างกันขนาดนั้น วิธีนับทุกแบบในโลกจริงมีอัตราความผิดพลาดที่ไม่เป็นศูนย์ ดังนั้นในบริบทส่วนใหญ่สองคำนี้ใช้แทนกันได้
      เช่น ในการเลือกตั้งเราพูดว่า “นับคะแนน” แต่ถ้าคะแนนสูสี ก็จะ “นับใหม่” และคาดได้เต็มที่ว่าอาจได้ตัวเลขต่างจากจำนวนเดิมเล็กน้อย ถ้าอย่างนั้นการนับคะแนนก็แท้จริงแล้วเป็นการประมาณคะแนน และการนับใหม่ก็เป็นเพียงการประมาณที่มีขอบเขตความผิดพลาดแคบลง
      ตำนาน “countless stones” (https://en.wikipedia.org/wiki/Countless_stones) ก็ให้ความรู้สึกเหมือนเป็นเครื่องเตือนใจแบบชาวบ้านว่า แม้แต่สิ่งที่ใหญ่ แข็ง และคงที่อย่างหินตั้ง ก็ยังไม่ควรมั่นใจเกินไปว่าได้นับอย่างถูกต้องแล้ว
      กรณีที่การนับไม่ใช่การประมาณน่าจะจำกัดอยู่แค่สถานการณ์ทางคณิตศาสตร์ คือเมื่อสามารถรับประกันได้ว่าจัดการครบทุก item โดยไม่ตกหล่น และไม่ได้สับสนตัวตนของ item ใดกับอีก item หนึ่ง
    • สำหรับตัวเลขที่ค่อนข้างเล็กก็ถูก แต่สำหรับตัวเลขที่ใหญ่มาก โดยทั่วไป การประมาณถือว่าเทียบเท่ากับการนับ และผลลัพธ์อาจไม่ได้แสดงเป็นจำนวนเต็ม แต่แสดงด้วยสัญกรณ์วิทยาศาสตร์ หรือเหมือนเลขทศนิยมลอยตัว
      ตัวอย่างเช่น mole เป็นจำนวนเต็ม แต่ค่าของมันก็รู้ได้เพียงโดยประมาณ และไม่มีใครใส่ใจกับค่าที่แน่นอน
    • นี่ไม่ใช่ estimation แต่เป็น approximation

  • ชอบตัวอย่างการ คิดนอกกรอบ แบบนี้มาก โดยเฉพาะเพราะเป็นสิ่งที่ตัวเองไม่ค่อยถนัดในงานด้วย สิ่งสำคัญไม่ใช่แค่การเรียนรู้วิธีแก้ปัญหาที่ถูกต้อง แต่คือกระบวนการค้นหาคำถามที่ทำให้ปัญหาที่มีอยู่ง่ายขึ้น หรือบางครั้งทำให้แก้ได้เลย
    ในกรณีนี้ คำถามสำคัญคือ “ไม่จำเป็นต้องได้ตัวเลขที่แม่นยำ แค่กำหนดช่วงความน่าจะเป็นภายในพารามิเตอร์ที่นิยามไว้ก็พอ” สำหรับปัญหาอื่นก็ย่อมมีคำถามอื่น หวังว่าถ้าได้เห็นตัวอย่างแบบนี้มากพอ จะสามารถซึมซับกระบวนการคิดและนำไปใช้ได้อย่างถูกต้อง

    • ถ้าจะพูดอย่างเป็นธรรม เรื่องนี้เป็นผลงานของทีมวิจัยมหาวิทยาลัย เป็นทีมของคนที่สามารถใช้เวลาทั้งวันทบทวนหัวข้อเดียวซ้ำ ๆ ด้วยวิธีการทางวิทยาศาสตร์ได้จริง ๆ
      ถ้าคุณได้รับเงินให้นั่งหน้าไวต์บอร์ดทั้งวันกับวิศวกรที่ฉลาดพอ ๆ กันในบริษัทใหญ่ ก็น่าจะสร้างอะไรบางอย่างที่คนทั่วไปมองว่าเป็น “วิธีแก้นอกกรอบ” ได้แน่นอน
      แต่พวกเราส่วนใหญ่ได้รับเงินให้ทำงานใน สายการผลิต JIRA จึงมีเวลาจำกัดสำหรับการเกาะปัญหาเดียวแล้วทดลองไปเรื่อย ๆ
    • ปกติน่าจะเรียกว่า การคิดเชิงแนวข้าง Edward de Bono เขียนหนังสือเกี่ยวกับเรื่องนี้ไว้หลายเล่ม อาจน่าสนใจ

  • ตัวอย่างอย่าง “ถ้าอยากนับจำนวนผู้ใช้ที่แตกต่างกันซึ่งล็อกอิน Facebook ในแต่ละวัน และผู้ใช้บางคนล็อกอินจากหลายอุปกรณ์และหลายช่วงเวลา?” ดูไม่ค่อยเหมือนสถานการณ์ที่อัลกอริทึมนี้มีประโยชน์จริงเท่าไร
    ถ้าตอนออกแบบกระบวนการล็อกอินรู้อยู่แล้วว่าต้องใช้ข้อมูลนี้ ก็ทำได้ง่าย ๆ คือบันทึกวันที่ล็อกอินล่าสุดของแต่ละบัญชี แล้วเพิ่มตัวนับผู้ใช้แบบไม่ซ้ำเฉพาะเมื่อค่าที่บันทึกไว้ต่างจากวันที่ปัจจุบัน
    ต่อให้ไม่ใช่แบบนั้น ภายหลังก็น่าจะสามารถ “replay” สตรีมเหตุการณ์ล็อกอินจากฐานข้อมูลเพื่อวิเคราะห์ได้ กรณีที่มีข้อมูลสะสมมาหลายปีแล้วอาจเป็นอีกเรื่องหนึ่ง

    • วิธีนั้นต้องติดตาม “วันที่ล็อกอินล่าสุดของแต่ละบัญชี” จึงต้องใช้หน่วยความจำตามจำนวนผู้ใช้ แก่นของอัลกอริทึมนี้คือทำได้ด้วย หน่วยความจำคงที่ ที่เล็กกว่ามาก

  • พูดถึงเรื่องการนับ อยากกล่าวถึงอัลกอริทึมที่มีประสิทธิภาพและยังนำไปใช้งานได้ง่ายสำหรับการหา รายการ top k ในสตรีม ดูเหมือนจะไม่ค่อยเป็นที่รู้จักเท่าที่ควร
    A Simple Algorithm for Finding Frequent Elements in Streams and Bags
    Karp, Shenker & Papadimitriou
    https://www.cs.umd.edu/~samir/498/karp.pdf

    • สำนวนว่า “รายการ top k ในสตรีม” ฟังดูต่างจากคำอธิบายในบทคัดย่อ บทคัดย่อบอกว่าเป็นการหา สัญลักษณ์ที่มีความถี่สูงกว่าเกณฑ์ที่กำหนด ในสตริงสัญลักษณ์ที่ยาวมากจากอัลฟาเบ็ตขนาดใหญ่
      คำอธิบายของคุณฟังเหมือนเป็นการหารายการจำนวน k รายการแบบคงที่ และรับประกันว่าพวกมันต้องเป็นอันดับบนสุด แต่บทคัดย่อฟังเหมือนเป็นการหารายการที่มีจำนวนไม่ทราบล่วงหน้า ซึ่งเข้าเงื่อนไขว่ามากกว่าค่า k บางค่า
      มันดูเหมือนความต่างระหว่าง “หาผู้ใช้ที่อายุมากที่สุด 100 คน” กับ “หาผู้ใช้ทุกคนที่อายุเกิน 30 ปี” หรือว่าผมเข้าใจคำพูดของคุณหรือบทคัดย่อผิดไป? ภาษาอังกฤษไม่ใช่ภาษาแม่ เลยสับสน

  • นักวิทยาการคอมพิวเตอร์คิดค้นวิธี ประมาณ ขนาดของสับเซตอย่างประหยัดหน่วยความจำสินะ

    • ถ้าสามารถได้ค่าประมาณด้วยการโยนเหรียญน้อยรอบลง ก็ดูเหมือนจะเร็วขึ้นด้วย อาจไม่จำเป็นต้องไล่อ่าน “หนังสือ” ทั้งเล่มจนจบเพื่อประมาณจำนวนคำที่แตกต่างกัน
    • ตรงนี้สับเซตเป็นประเด็นสำคัญ นั่นคือ สับเซตขององค์ประกอบที่ไม่ซ้ำกัน