algorithm আটত 1 এমবি র্যামে 1 মিলিয়ন 8-সংখ্যা সংখ্যার ক্রম




১ বিলিয়ন সংখ্যায় প্রকাশ (24)

আমার কম্পিউটারে 1 এমবি র্যাম এবং অন্য কোনও স্থানীয় স্টোরেজ নেই। আমি এটি একটি টিসিপি সংযোগের উপর 1 মিলিয়ন 8-ডিজিট সংখ্যার গ্রহণ করতে ব্যবহার করতে হবে, তাদের সাজান, এবং তারপর সাজানো তালিকাটি অন্য টিসিপি সংযোগে প্রেরণ করুন।

সংখ্যার তালিকাতে ডুপ্লিকেট থাকতে পারে, যা আমাকে বাতিল করতে হবে না। কোডটি রমতে স্থাপন করা হবে, তাই আমার 1 MB থেকে আমার কোডের আকার কমানোর দরকার নেই। আমার ইতিমধ্যে ইথারনেট পোর্ট চালানোর এবং টিসিপি / আইপি সংযোগগুলিকে পরিচালনা করার কোড আছে এবং এর জন্য 1 কেবি বাফার সহ 2 কিলার প্রয়োজন, যার মাধ্যমে কোডটি পড়বে এবং তথ্য লিখবে। এই সমস্যার কি কোন সমাধান আছে?

প্রশ্ন এবং উত্তর উত্স:
slashdot.org

cleaton.net


Answer #1

আমি একটি রেডিক্স ট্রি চেষ্টা করবে । আপনি যদি কোনও গাছের মধ্যে তথ্য সংরক্ষণ করতে পারেন তবে আপনি ডাটা প্রেরণ করতে একটি ইন-অর্ডার ট্র্যাভশ করতে পারেন।

আমি নিশ্চিত নই যে আপনি 1 মেগাবাইটে ফিট করতে পারবেন, কিন্তু আমি মনে করি এটি একটি মূল্যের।


Answer #2

এখানে কিছু সমাধান সি ++ কোড যা সমস্যা সমাধান করে।

মেমরি সীমাবদ্ধতা সন্তুষ্ট যে প্রুফ:

সম্পাদক: এই পোস্টে বা তার ব্লগে লেখক দ্বারা সর্বাধিক মেমরির প্রয়োজনীয়তাগুলির কোন প্রমাণ নেই। যেহেতু একটি মান এনকোড করার জন্য প্রয়োজনীয় বিট সংখ্যা পূর্বে এনকোড করা মানগুলির উপর নির্ভর করে, তাই এই প্রমাণটি সম্ভবত অ-তুচ্ছ। লেখক নোট করেছেন যে তিনি অভিজ্ঞতার ভিত্তিতে সবচেয়ে বড় এনকোডেড আকার 1011732 ছিল, এবং 1013000 বাফার আকার 1013000 বেছে নেন।

typedef unsigned int u32;

namespace WorkArea
{
    static const u32 circularSize = 253250;
    u32 circular[circularSize] = { 0 };         // consumes 1013000 bytes

    static const u32 stageSize = 8000;
    u32 stage[stageSize];                       // consumes 32000 bytes

    ...

একসঙ্গে, এই দুই অ্যারে সঞ্চয় 1045000 বাইট গ্রহণ। যে 1048576 - 1045000 - 2 × 1024 = 1528 বাইট বাকি ভেরিয়েবল এবং স্ট্যাক স্থান জন্য পাতা।

এটা আমার Xeon W3520 উপর প্রায় 23 সেকেন্ডে রান। আপনি প্রোগ্রামটি নিম্নোক্ত পাইথন স্ক্রিপ্ট ব্যবহার করে কাজটি যাচাই করতে পারেন, sort1mb.exe প্রোগ্রাম নামটি sort1mb.exe

from subprocess import *
import random

sequence = [random.randint(0, 99999999) for i in xrange(1000000)]

sorter = Popen('sort1mb.exe', stdin=PIPE, stdout=PIPE)
for value in sequence:
    sorter.stdin.write('%08d\n' % value)
sorter.stdin.close()

result = [int(line) for line in sorter.stdout]
print('OK!' if result == sorted(sequence) else 'Error!')

নিম্নলিখিত সিরিজগুলিতে অ্যালগরিদমের বিস্তারিত ব্যাখ্যা পাওয়া যেতে পারে:


Answer #3

যদি ইনপুট স্ট্রিমটি কয়েকবার গ্রহণ করা যেতে পারে তবে এটি আরও সহজ হবে (যে সম্পর্কে, ধারণা এবং সময়-কর্মক্ষমতা সমস্যা সম্পর্কে কোন তথ্য নেই)। তারপর, আমরা দশমিক মান গণনা করতে পারে। গণনা মান সঙ্গে আউটপুট স্ট্রিম করতে সহজ হবে। মান গণনা দ্বারা কম্প্রেস। এটা ইনপুট স্ট্রিম কি হবে তা নির্ভর করে।


Answer #4

সাজানো অ্যারের প্রতিনিধিত্ব করার জন্য শুধুমাত্র প্রথম উপাদান এবং সংলগ্ন উপাদানের মধ্যে পার্থক্য সংরক্ষণ করতে পারে। এইভাবে আমরা 10 ^ 6 টি উপাদান এনকোডিং নিয়ে উদ্বিগ্ন যা সর্বাধিক 10 ^ 8 এ যোগ করতে পারে। আসুন এই ডি কল । ডি এর উপাদান এনকোড করতে একটি হাফম্যান কোড ব্যবহার করতে পারেন । হাফম্যান কোডের জন্য অভিধানটি তৈরি করা যেতে পারে এবং অ্যারে যখন সাজানো অ্যারে (সন্নিবেশ সাজানোর) সন্নিবেশ করা হয় তখন প্রতিবার নতুন আইটেম সন্নিবেশ করা হয়। নোট করুন যে যখন একটি নতুন আইটেমের কারণে অভিধানটি পরিবর্তন হয় তখন নতুন অ্যারোডিংটির সাথে মেলে সম্পূর্ণ অ্যারে আপডেট করা উচিত।

ডি প্রতিটি উপাদান এনকোডিং জন্য বিট গড় সংখ্যা যদি আমাদের প্রতিটি অনন্য উপাদান সমান সংখ্যা আছে সর্বাধিক। উপাদান বলুন D1 , D2 , ..., ডিএন মধ্যে ডি প্রতিটি প্রদর্শিত এফ বার। যে ক্ষেত্রে (সবচেয়ে খারাপ ক্ষেত্রে আমরা ইনপুট ক্রম উভয় 0 এবং 10 ^ 8 আছে) আমরা আছে

সমষ্টি (1 <= আমি <= এন ) এফডি = 10 ^ 8

কোথায়

সমষ্টি (1 <= i <= N ) F = 10 ^ 6, বা F = 10 ^ 6 / N এবং স্বাভাবিককৃত ফ্রিকোয়েন্সি হবে = = F / 10 ^ = 1 / N

বিট গড় সংখ্যা হবে -log2 (1 / পি ) = log2 ( এন )। এই পরিস্থিতিতে আমরা একটি কেস যে maximizes এন খুঁজে পেতে হবে । যদি সেটা হয় আমরা জন্য পরপর নম্বর আছে দ্বি 0 থেকে শুরু, বা, দ্বি = আমি -1, অতএব

10 ^ 8 = SUM (1 <= আমি <= এন ) এফdi = sum (1 <= i <= N ) (10 ^ 6 / N ) (i-1) = (10 ^ 6 / N ) N ( N -1) / 2

অর্থাত

N <= 201. এবং এই ক্ষেত্রে বিটগুলির গড় সংখ্যা হল log2 (201) = 7.6511 যার অর্থ হল সাজানোর অ্যারে সংরক্ষণের জন্য আমাদের প্রায় 1 বাইট প্রতি ইনপুট উপাদান প্রয়োজন। উল্লেখ্য, ডি সাধারণভাবে 201 টিরও বেশি উপাদান থাকতে পারে না। এটি শুধুমাত্র বীজ বন্টন করে যদি ডি- এর উপাদানগুলি সমানভাবে বিতরণ করা হয়, তবে এটি 201 টির বেশি অনন্য মানের হতে পারে না।


Answer #5

আমি মনে করি এটি সম্পর্কে চিন্তা করার এক উপায় একটি যৌগিক দৃষ্টিভঙ্গি থেকে: সাজানো নম্বর ক্রমগুলির কতগুলি সম্ভাব্য সমন্বয় রয়েছে? যদি আমরা সমন্বয় 0,0,0, ...., 0 কোড 0, এবং 0,0,0, ... 1, কোড 1, এবং 9999 9999, 9999 9999, ... 9999 9999 কোড এন, এন কি? অন্য কথায়, ফলাফল স্থান কত বড়?

আচ্ছা, এই বিষয়ে চিন্তা করার এক উপায় এই যে এটি একটি এক্স এক্স এম গ্রিডের এককোণিক পাথের সংখ্যা খুঁজে বের করার সমস্যাটির একটি বিজয়ের উদাহরণ যেখানে N = 1,000,000 এবং M = 100,000,000। অন্য কথায়, যদি আপনার একটি গ্রিড রয়েছে যা 1,000,000 প্রশস্ত এবং 100,000,000 লম্বা, নীচের দিক থেকে বাম দিক থেকে বাম দিকের কততম ছোট পথ আছে? কোর্সের সর্বনিম্ন পথগুলির জন্য আপনাকে কেবলমাত্র ডান বা উপরে সরানো দরকার (যদি আপনি সরাতে বা বামে যান তবে পূর্বে সম্পন্ন অগ্রগতিটি পূর্বাবস্থায় ফিরিয়ে আনা হবে)। আমাদের সংখ্যা সাজানোর সমস্যাটি কীভাবে এটি একটি বিজেকশন দেখতে, নিম্নলিখিতটি লক্ষ্য করুন:

আপনি আমাদের ক্রম সংখ্যায় আমাদের অনুভূমিক পাটি কল্পনা করতে পারেন, যেখানে পাটির অবস্থান Y প্রতিনিধিত্ব করে।

তাই যদি পথটি ঠিক পথে ডান দিকে চলে যায়, তাহলে উপরের দিকে চলে যায়, যা 0,0,0, ..., 0 এর সমান। এর পরিবর্তে এটি শীর্ষে সমস্ত পথে জাম্পিং করে শুরু করে এবং তারপর 1,000,000 বার ডান দিকে চলে যায়, যা 99 9999 999999999999 এর সমতুল্য, ..., 99999999। একটি পথ যেখানে এটি একবার একবার চলে যায়, তারপরে একবার সঠিক হয় , তারপর শেষ পর্যন্ত, ইত্যাদি খুব শেষ পর্যন্ত (তারপরে সর্বোপরি উপরের দিকে চলে যায়), 0,1,2,3, ..., 999999 এর সমতুল্য।

সৌভাগ্যক্রমে আমাদের জন্য এই সমস্যাটি সমাধান করা হয়েছে, যেমন একটি গ্রিড আছে (N + M) চয়ন করুন (এম) পাথগুলি:

(1,000,000 + 100,000,000) চয়ন করুন (100,000,000) ~ = 2.27 * 10 ^ 2436455

N এভাবে 2.27 * 10 ^ 2436455 সমান, এবং তাই 0 কোডটি 0,0,0, ..., 0 এবং কোড 2.27 * 10 ^ 2436455 প্রতিনিধিত্ব করে এবং কিছু পরিবর্তন 99 999999,9999 9999, ..., 99999999 প্রতিনিধিত্ব করে।

0 থেকে 2.27 * 10 ^ 2436455 পর্যন্ত সমস্ত নম্বর সংরক্ষণ করার জন্য আপনাকে lg2 (2.27 * 10 ^ 2436455) = 8.0937 * 10 ^ 6 বিট প্রয়োজন।

1 মেগাবাইট = 8388608 বিট> 8093700 বিট

তাই মনে হচ্ছে আমরা অন্তত প্রকৃতপক্ষে পর্যাপ্ত পরিমাণে রুম সংরক্ষণ করতে পারি! এখন অবশ্যই আকর্ষণীয় বিটটি সংখ্যায় প্রবাহ হিসাবে সাজানোর কাজ করছে। নিশ্চিত নয় যে এর সর্বোত্তম পদ্ধতিতে আমাদের ২২4908 বিট বাকি আছে। আমি কল্পনা করি যে প্রতিটি বিন্দুতে প্রত্যেকটি বিন্দুতে একটি কৌশলগত কৌশল রয়েছে যা ধরে নেওয়া হয় যে এটি হল সম্পূর্ণ আদেশ, সেই ক্রমটির কোডটি খুঁজে বের করা, এবং তারপরে আপনি একটি নতুন নম্বর ফিরে যাচ্ছেন এবং পূর্ববর্তী কোডটি আপডেট করছেন। হাত তরঙ্গ হাত তরঙ্গ।


Answer #6

আপনি ক্রম সংখ্যার মধ্যে পার্থক্য সংরক্ষণ করতে হবে, এবং এই ক্রম সংখ্যার কম্প্রেস করার জন্য এনকোডিং ব্যবহার করুন। আমাদের 2 ^ 23 বিট আছে। আমরা 6 বিট অংশে বিভক্ত করব, এবং শেষ বিটটি নির্দেশ করবে যে সংখ্যাটি অন্য 6 বিট (5 বিট প্লাস প্রসারিত অংশ) প্রসারিত হবে কিনা তা নির্দেশ করে।

সুতরাং, 000010 হল 1, এবং 000100 ২। 000001100000 128। এখন, আমরা 10,000,000 পর্যন্ত সংখ্যার ক্রম অনুসারে পার্থক্য উপস্থাপন করতে সবচেয়ে খারাপ কাস্ট বিবেচনা করি। 10,000,000 / 2 ^ 2 পার্থক্য 2 ^ 5, 10,000,000 / 2 ^ 2 ^ 10 এর চেয়ে 10 পার্থক্য বেশি হতে পারে, এবং 10,000,000 / 2 ^ 15 ^ 2 থেকে 15 পার্থক্য বেশী।

সুতরাং, আমরা আমাদের ক্রম প্রতিনিধিত্ব করতে কতটুকু লাগবে তা যোগ করে। আমাদের 1,000,000 * 6+ রাউন্ডআপ (10,000,000 / ২ ^ 5) * 6+ রাউন্ডআপ (10,000,000 / ২ ^ 10) * 6+ রাউন্ডআপ (10,000,000 / ২ ^ 15) * 6+ রাউন্ডআপ (10,000,000 / ২ ^ ২0) * 4 = 7935479।

2 ^ 24 = 8388608. 8388608> 7935479 থেকে, আমাদের সহজে যথেষ্ট মেমরি থাকা উচিত। আমরা নতুন সংখ্যা সন্নিবেশ করা হয় যেখানে সমষ্টি সঞ্চয় করার জন্য সম্ভবত আমাদের স্মৃতির একটি সামান্য বিট দরকার। তারপর আমরা ক্রম মাধ্যমে যান, এবং আমাদের নতুন নম্বর সন্নিবেশ করা যেখানে খুঁজে, প্রয়োজন হলে পরবর্তী পার্থক্য হ্রাস, এবং ডান পরে সবকিছু স্থানান্তর।


Answer #7

রেডিক্স ট্রি উপস্থাপনাটি এই সমস্যাটি পরিচালনা করার কাছাকাছি আসবে, কারণ রেডিক্স গাছটি "উপসর্গ সংকোচনের" সুবিধা নেয়। কিন্তু একটি রেডিক্স গাছ প্রতিনিধিত্বের ধারণা করা কঠিন, যা এক বাইটের মধ্যে একটি নোডের প্রতিনিধিত্ব করতে পারে - সম্ভবত এটি সীমা সম্পর্কে।

কিন্তু, তথ্যটি কীভাবে উপস্থাপিত হয় তা নির্বিশেষে, এটি সাজানোর পরে এটি উপসর্গ-সংকুচিত ফর্মের মধ্যে সংরক্ষণ করা যেতে পারে, যেখানে সংখ্যা 10, 11, এবং 12 প্রতিনিধিত্ব করবে, 001b, 001b, 001b, 1 এর বৃদ্ধি বৃদ্ধি করে আগের সংখ্যা থেকে। সম্ভবত, তারপর, 10101b 5 বৃদ্ধি, 1101001b 9 বৃদ্ধি, ইত্যাদি বৃদ্ধি প্রতিনিধিত্ব করবে।


Answer #8

গুগল এর (খারাপ) পদ্ধতি, এইচএন থ্রেড থেকে। দোকান RLE- শৈলী গণনা।

আপনার প্রাথমিক ডেটা গঠন হল '99999999: 0' (সমস্ত শূন্যতা, কোন সংখ্যা দেখিনি) এবং তারপরে বলুন আপনি 3,866,344 নম্বরটি দেখতে পান তাই আপনার ডেটা গঠন '3866343: 0,1: 1,96133654: 0' হয়ে যায়। সংখ্যাগুলি হ'ল শূন্য বিট সংখ্যা এবং '1' বিটের সংখ্যাগুলির মধ্যে সর্বদা বিকল্প থাকবে তাই আপনি অদ্ভুত সংখ্যাগুলি 0 বিট এবং এমনকি সংখ্যার 1 বিটগুলি প্রতিনিধিত্ব করতে পারেন। এটি হয়ে যায় (3866343,1,96133654)

তাদের সমস্যা ডুপ্লিকেটগুলি আবরণ বলে মনে হচ্ছে না, তবে তারা সদৃশগুলির জন্য "0: 1" ব্যবহার করে বলে।

বড় সমস্যা # 1: 1 এম ইন্টিজারের জন্য সন্নিবেশ বয়সের সময় নিতে হবে

বড় সমস্যা # 2: সমস্ত সমতল ডেল্টা এনকোডিং সমাধানগুলির মতো, কিছু বিতরণ এই ভাবে আচ্ছাদিত করা যাবে না। উদাহরণস্বরূপ, দূরত্ব 0:99 সহ 1 মি পূর্ণসংখ্যা (যেমন +99 প্রত্যেকটি)। এখন 0: 99 এর সীমার মধ্যে র্যান্ডম দূরত্বের সাথে একই ভাবুন । (দ্রষ্টব্য: 99999999/1000000 = 99.99)

গুগল এর পদ্ধতি উভয় অযোগ্য (ধীর) এবং ভুল। কিন্তু তাদের প্রতিরক্ষা, তাদের সমস্যা সামান্য ভিন্ন হতে পারে।


Answer #9

আমার কম্পিউটার 1 এম র্যাম এবং অন্য কোনও স্থানীয় স্টোরেজ নেই

প্রতারণার আরেকটি উপায়: আপনি তার পরিবর্তে অ-স্থানীয় (নেটওয়ার্কযুক্ত) সঞ্চয়স্থান ব্যবহার করতে পারেন (আপনার প্রশ্নটি এটিকে বাধা দেয় না) এবং একটি নেটওয়ার্কযুক্ত পরিষেবা কল করুন যা সরাসরি ডিস্ক-ভিত্তিক মার্জোর্ট্ট (অথবা কেবলমাত্র মেমরিতে সাজানোর জন্য যথেষ্ট RAM ব্যবহার করতে পারে) শুধুমাত্র 1M নম্বর গ্রহণ করতে হবে), প্রয়োজন ছাড়াই (স্বীকার করা অত্যন্ত চিত্তাকর্ষক) সমাধান ইতিমধ্যে।

এটি প্রতারণা হতে পারে, কিন্তু আপনি কোনও বিশ্ব-সমস্যা সমস্যার সমাধান খুঁজছেন নাকি এমন একটি ধাঁধা যা নিয়মগুলির নমুনাকে আমন্ত্রণ জানাচ্ছে তা যদি স্পষ্ট না হয় তবে ... কিন্তু "জেনুইন" সমাধান (যা অন্যদের নির্দেশ করেছে, কেবল কম্প্রেসযোগ্য ইনপুটগুলির জন্য কাজ করতে পারে)।


Answer #10

আমরা যদি সেই সংখ্যাগুলির সম্পর্কে কিছু জানি না, তবে আমরা নিম্নলিখিত সীমাবদ্ধতা দ্বারা সীমাবদ্ধ:

  • আমরা তাদের সাজানোর আগে আমরা সব নম্বর লোড করতে হবে,
  • সংখ্যার সেট কম্প্রেসযোগ্য নয়।

যদি এই ধারনাগুলি ধরে থাকে তবে আপনার কার্য সম্পাদন করার কোন উপায় নেই, আপনার কমপক্ষে 26,575,425 বিট সঞ্চয়স্থান (3,321, 9২২ বাইট) প্রয়োজন হবে।

আপনি আপনার তথ্য সম্পর্কে আমাদের কি বলতে পারেন?


Answer #11

বাছাই এখানে একটি দ্বিতীয় সমস্যা। অন্য বলেন, শুধু পূর্ণসংখ্যা সংরক্ষণ করা কঠিন, এবং সমস্ত ইনপুটগুলিতে কাজ করতে পারে না , কারণ 27 বিট প্রতি নম্বর প্রয়োজন হবে।

আমার উপর এইটি হল: ক্রমাগত (সাজানো) পূর্ণসংখ্যার মধ্যে কেবলমাত্র পার্থক্য সঞ্চয় করুন, কারণ এটি সম্ভবত ছোট হবে। তারপরে সংকোচন প্রকল্পটি ব্যবহার করুন, উদাহরণস্বরূপ ইনপুট সংখ্যা প্রতি 2 টি অতিরিক্ত বিট সহ, নম্বর কতগুলি বিট সংরক্ষণ করা হয় তা এনকোড করতে। কিছুটা এইরকম:

00 -> 5 bits
01 -> 11 bits
10 -> 19 bits
11 -> 27 bits

প্রদত্ত মেমরি সীমাবদ্ধতার মধ্যে সম্ভাব্য ইনপুট তালিকাগুলির একটি মোট সংখ্যা সংরক্ষণ করা সম্ভব। কম্প্রেশন স্কীমটি কীভাবে সর্বোচ্চ সংখ্যক ইনপুটগুলিতে কাজ করে তা গণিতের বাইরে, আমার বাইরে।

আমি আশা করি আপনি এই উপর ভিত্তি করে একটি ভাল যথেষ্ট পূর্ণসংখ্যা কম্প্রেশন প্রকল্প খুঁজে পেতে আপনার ইনপুট ডোমেন-নির্দিষ্ট জ্ঞান শোষণ করতে সক্ষম হতে পারে ।

ওহ এবং তারপর, আপনি তথ্য প্রাপ্ত হিসাবে আপনি সাজানো তালিকা উপর একটি সন্নিবেশ সাজানোর না।


Answer #12

আমি টিসিপি এর পুনর্মিলন আচরণ শোষণ করবে।

  1. টিসিপি কম্পোনেন্টটি বড় আকারের উইন্ডো তৈরি করুন।
  2. তাদের জন্য একটি ACK পাঠানো ছাড়া প্যাকেট কিছু পরিমাণ পান।
    • কিছু (উপসর্গ) সংকুচিত তথ্য গঠন তৈরি পাস পাস প্রক্রিয়া
    • শেষ প্যাকেটের জন্য ডুপ্লিকেট এ্যাক পাঠান যা আর প্রয়োজন নেই / পুনঃপ্রতিষ্ঠানের সময়সীমার জন্য অপেক্ষা করুন
    • Goto 2
  3. সমস্ত প্যাকেট গ্রহণ করা হয়

এই buckets বা একাধিক পাসের উপকার কিছু ধরনের অনুমান।

সম্ভবত ব্যাচ / বালতি বাছাই এবং তাদের মার্জ করে। -> রেডিক্স গাছ

প্রথম 80% গ্রহন এবং সাজানোর জন্য এই কৌশলটি ব্যবহার করুন এবং শেষ ২0% পড়ুন, যাচাই করুন যে শেষ ২0% সংখ্যায় সর্বনিম্ন সংখ্যার প্রথম ২0% জমে থাকা সংখ্যাগুলি যাচাই করে না। তারপরে 20% সর্বনিম্ন নম্বর পাঠান, মেমরি থেকে সরিয়ে দিন, বাকি ২0% নতুন সংখ্যা এবং একত্রিত করুন। **


Answer #13

আমাদের 1 এমবি আছে - 3 কেবি RAM = 2 ^ 23 - 3 * 2 ^ 13 বিট = 8388608 - 24576 = 8364032 বিট উপলব্ধ।

আমরা 10 ^ 8 পরিসরে 10 ^ 6 সংখ্যার প্রদত্ত। এটি ~ 100 <2 ^ 7 = 128 এর গড় ফাঁক দেয়

আসুন প্রথমে প্রথমে সমানভাবে সমান্তরাল সংখ্যাগুলির সহজ সমস্যাটি বিবেচনা করি যখন সমস্ত ফাঁকগুলি <128। এটি সহজ। শুধু প্রথম সংখ্যা এবং 7-বিট ফাঁকগুলি সংরক্ষণ করুন:

(27 বিট) + 10 ^ 6 7-বিট ফাঁক সংখ্যা = 7000027 বিট প্রয়োজন

নোট পুনরাবৃত্তি সংখ্যা 0 ফাঁক আছে।

কিন্তু যদি আমাদের 127 এর চেয়ে বড় ফাঁক থাকে?

ঠিক আছে, একটি গালি আকার <127 প্রতিনিধিত্ব করে সরাসরি বলুন, কিন্তু 127 এর ফাঁক আকার প্রকৃত ফাঁক দৈর্ঘ্যের জন্য একটি 8-বিট এনকোডিং দ্বারা অনুসরণ করা হয়:

 10xxxxxx xxxxxxxx                       = 127 .. 16,383
 110xxxxx xxxxxxxx xxxxxxxx              = 16384 .. 2,097,151

প্রভৃতি

উল্লেখ্য, এই সংখ্যা প্রতিনিধিত্বটি তার নিজস্ব দৈর্ঘ্য বর্ণনা করে যাতে আমরা জানি যে পরবর্তী ফাঁকা সংখ্যাটি কখন শুরু হয়।

শুধুমাত্র ছোট ফাঁক দিয়ে <127, এটি এখনও 7000027 বিট প্রয়োজন।

পর্যন্ত হতে পারে (10 ^ 8) / (2 ^ 7) = 781250 23-বিট ফাঁক সংখ্যা, অতিরিক্ত 16 * 781,250 = 12,500,000 বিট প্রয়োজন যা অনেক বেশি। আমরা একটি আরো কমপ্যাক্ট এবং ধীরে ধীরে ফাঁক বৃদ্ধি উপস্থাপনা প্রয়োজন।

গড় ফাঁক আকার 100 হয় তাই যদি আমরা তাদের [100, 99, 101, 98, 102, ..., 2, 198, 1, 199, 0, 200, 201, ২0২, ...] হিসাবে পুনর্বিন্যাস করি এবং এটি সূচী করি '00' দ্বারা সীমিত সংখ্যাসূচক সংখ্যার সাথে জোড়ার কোন জোড়া সহ (উদাহরণস্বরূপ, 11011 = 8 + 5 + 2 + 1 = 16) একটি ঘন বাইনারি ফিবোনাসি বেস এনকোডিং সহ আমি মনে করি আমরা যথেষ্ট পরিমাণে ফাঁক উপস্থাপনাটি রাখতে পারি, তবে এটির প্রয়োজন আরো বিশ্লেষণ।


Answer #14

গিলম্যানভের উত্তর তার ধারণার মধ্যে খুব ভুল। এটি একটি মিলিয়ন ক্রমাগত পূর্ণসংখ্যার একটি নিরবধি পরিমাপ ভিত্তিক অনুমান শুরু হয়। যে কোন ফাঁক মানে। যারা র্যান্ডম ফাঁক, তবে ছোট, সত্যিই এটি একটি দরিদ্র ধারণা তোলে।

এটি নিজে চেষ্টা করো. 1 মিলিয়ন র্যান্ডম 27 বিট পূর্ণসংখ্যা পান, তাদের সাজান, 7-Zip , xz, আপনি LZMA যাই হোক না কেন যাই হোক না কেন সংকুচিত। ফলাফল 1.5 এমবি বেশি। উপরে প্রাঙ্গন ক্রমিক সংখ্যা সংকোচনের হয়। এমনকি ডেল্টা এনকোডিং যে 1.1 এমবি বেশি । এবং এই কম্প্রেস জন্য 100 এমবি র্যাম ব্যবহার করে মনে রাখবেন না। তাই এমনকি সংকুচিত পূর্ণসংখ্যা সমস্যা মাপসই না এবং রান সময় RAM ব্যবহার মনে রাখবেন না

এটা আমাকে খুব খারাপ করে তোলে যে লোকেরা কীভাবে সুন্দর গ্রাফিক্স এবং যুক্তিবিজ্ঞানকে তুলে ধরে।

#include <stdint.h>
#include <stdlib.h>
#include <time.h>

int32_t ints[1000000]; // Random 27-bit integers

int cmpi32(const void *a, const void *b) {
    return ( *(int32_t *)a - *(int32_t *)b );
}

int main() {
    int32_t *pi = ints; // Pointer to input ints (REPLACE W/ read from net)

    // Fill pseudo-random integers of 27 bits
    srand(time(NULL));
    for (int i = 0; i < 1000000; i++)
        ints[i] = rand() & ((1<<27) - 1); // Random 32 bits masked to 27 bits

    qsort(ints, 1000000, sizeof (ints[0]), cmpi32); // Sort 1000000 int32s

    // Now delta encode, optional, store differences to previous int
    for (int i = 1, prev = ints[0]; i < 1000000; i++) {
        ints[i] -= prev;
        prev    += ints[i];
    }

    FILE *f = fopen("ints.bin", "w");
    fwrite(ints, 4, 1000000, f);
    fclose(f);
    exit(0);

}

এখন LZMA দিয়ে ints.bin কম্প্রেস ...

$ xz -f --keep ints.bin       # 100 MB RAM
$ 7z a ints.bin.7z ints.bin   # 130 MB RAM
$ ls -lh ints.bin*
    3.8M ints.bin
    1.1M ints.bin.7z
    1.2M ints.bin.xz

Answer #15

এই টাস্ক সম্ভব। আউটপুট এর আগে, মিলিয়ন সাজানো সংখ্যার মধ্যে একটি মেমরি উপস্থাপনা থাকবে। সেখানে কতগুলো ভিন্ন উপস্থাপনা আছে? যেহেতু সংখ্যার পুনরাবৃত্তি হতে পারে আমরা nCr (চয়ন করুন) ব্যবহার করতে পারবেন না, কিন্তু একটি অপারেশন multichoose যে কাজ করে বলা হয় multisets

  • আছে 2.2e2436455 পরিসীমা 0..99,999,999 একটি মিলিয়ন নম্বর নির্বাচন করার উপায়।
  • এর জন্য প্রতি সম্ভাব্য সমন্বয় বা 1,011,717 বাইট উপস্থাপন করতে 8,093,730 বিট প্রয়োজন ।

সুতরাং তাত্ত্বিকভাবে এটি সম্ভব হতে পারে, যদি আপনি সংখ্যার সাজানো তালিকার একটি সরল (যথেষ্ট) উপস্থাপনা নিয়ে আসতে পারেন। উদাহরণস্বরূপ, একটি উন্মাদ প্রতিনিধিত্বের জন্য 10MB অনুসন্ধানের টেবিল বা কোডগুলির লাইনের হাজার হাজার প্রয়োজন হতে পারে।

যাইহোক, "1 এম র্যাম" যদি এক মিলিয়ন বাইট মানে, তাহলে স্পষ্টতই পর্যাপ্ত স্থান নেই। 5% বেশি মেমরি এটি তাত্ত্বিকভাবে সম্ভব করে তোলে যে উপস্থাপনা খুব দক্ষ এবং সম্ভবত বর্বর হতে হবে না।


Answer #16

10 ^ 8 এর পরিধিতে 10 ^ 6 মান রয়েছে, তাই গড়ে প্রতি শত কোড কোড একটি মান রয়েছে। Nth পয়েন্ট থেকে N (1 + 1) পর্যন্ত দূরত্বটি সংরক্ষণ করুন। ডুপ্লিকেটের মান 0. এর একটি ছাড় আছে। এর অর্থ এই যে, স্কিপের জন্য সঞ্চয় করার জন্য কেবলমাত্র 7 বিটের কম গড় প্রয়োজন, তাই তাদের মধ্যে এক মিলিয়ন সুখীভাবে আমাদের 8 মিলিয়ন বিট সঞ্চয়স্থান মাপসই করা হবে।

এই skips একটি বিটস্ট্রিম মধ্যে এনকোড করা প্রয়োজন, Huffman এনকোডিং দ্বারা বলুন। সন্নিবেশ নতুন মান পরে বিটস্ট্রীম এবং পুনর্লিখন মাধ্যমে পুনরাবৃত্তি দ্বারা হয়। মাধ্যমে পুনরাবৃত্তি এবং অন্তর্নিহিত মান লেখা আউটপুট। বাস্তবতার জন্য, সম্ভবত, 10 ^ 4 তালিকাগুলি 10 ^ 4 কোড পয়েন্ট (এবং 100 টির গড়ের গড়) আচ্ছাদিত করে বলতে পারে।

র্যান্ডম ডেটার জন্য একটি ভাল হাফম্যান গাছটি স্কিপগুলির দৈর্ঘ্যতে একটি পুইসন বন্টন (গড় = বৈকল্পিক = 100) অনুমান করে অগ্রিম তৈরি করা যেতে পারে, তবে প্রকৃত পরিসংখ্যান ইনপুটতে রাখা যেতে পারে এবং এর সাথে মোকাবিলা করার জন্য একটি সর্বোত্তম গাছ তৈরি করতে ব্যবহার করা যেতে পারে রোগ সংক্রান্ত ক্ষেত্রে।


Answer #17

আপনি কি ধরনের কম্পিউটার ব্যবহার করছেন? এটির কোনও "স্বাভাবিক" স্থানীয় সঞ্চয়স্থান থাকতে পারে না, তবে এটিতে ভিডিও RAM আছে কি? 1 মেগাপিক্সেল x 32 বিট প্রতি পিক্সেল (বলুন) আপনার প্রয়োজনীয় তথ্য ইনপুট আকারের কাছে বেশ কাছাকাছি।

(আমি মূলত পুরাতন অ্যাকোরন RISC পিসি এর স্মৃতিতে জিজ্ঞাসা করি , যেটি যদি কম রেজোলিউশন বা কম রঙের গভীরতার স্ক্রীন মোড চয়ন করে তবে উপলব্ধ সিস্টেম RAM সম্প্রসারিত করতে VRAM ধার্য করতে পারে!)। এটি কেবলমাত্র কয়েক এমবি স্বাভাবিক RAM সহ একটি মেশিনে উপযোগী ছিল।


Answer #18

প্রথম সঠিক উত্তর বা গাণিতিক এনকোডিং সঙ্গে উত্তর উত্তর দয়া করে দেখুন। নীচে আপনি কিছু মজা পাবেন, কিন্তু 100% বুলেট-প্রমাণ সমাধান নয়।

এটি বেশ আকর্ষণীয় কাজ এবং এখানে অন্য একটি সমাধান। আমি আশা করি কেউ ফলাফলটি কার্যকর করবে (অথবা অন্তত আকর্ষণীয়)।

পর্যায় 1: প্রাথমিক তথ্য গঠন, রুক্ষ কম্প্রেশন পদ্ধতি, মৌলিক ফলাফল

আসুন কিছু সহজ গণিত করি: আমাদের কাছে 10 এম (1048576 বাইট) RAM প্রাথমিকভাবে 10 ^ 6 8 ডিজিট সংখ্যা সঞ্চয় করার জন্য উপলব্ধ। [0; 99999999]। সুতরাং একটি সংখ্যা 27 বিট সংরক্ষণ করার প্রয়োজন হয় (স্বাক্ষরিত সংখ্যা ব্যবহার করা হবে যে অনুমিতি গ্রহণ)। সুতরাং, একটি কাঁচা স্ট্রিম ~ 3.5 এম র্যাম সংরক্ষণ করতে হবে। কেউ ইতিমধ্যে বলেছে এটা সম্ভবপর বলে মনে হচ্ছে না, তবে ইনপুট "যথেষ্ট ভাল" হলে কাজটি সমাধান করা যেতে পারে। মূলত, ধারণা কম্প্রেশন ফ্যাক্টর 0.29 বা উচ্চতর সঙ্গে ইনপুট ডেটা সংকুচিত হয় এবং সঠিকভাবে বাছাই করা।

এর প্রথম সংকোচনের সমস্যা সমাধান করা যাক। ইতিমধ্যে উপলব্ধ কিছু প্রাসঙ্গিক পরীক্ষা আছে:

http://www.theeggeadventure.com/wikimedia/index.php/Java_Data_Compression

"আমি কম্প্রেশন বিভিন্ন ফর্ম ব্যবহার করে ক্রমাগত এক মিলিয়ন পূর্ণসংখ্যা কম্প্রেস একটি পরীক্ষা দৌড়ে। ফলাফল নিম্নরূপ:"

None     4000027
Deflate  2006803
Filtered 1391833
BZip2    427067
Lzma     255040

এটি LZMA ( Lemel-Ziv-Markov শৃঙ্খলা অ্যালগরিদম ) এর মত দেখতে ভাল পছন্দ। আমি একটি সহজ পিওসি প্রস্তুত করেছি, কিন্তু এখনও কিছু বিশদ হাইলাইট করা আছে:

  1. মেমরি সীমাবদ্ধ তাই ধারণা সংখ্যা নির্ধারণ করা এবং অস্থায়ী সংগ্রহস্থল হিসাবে সংকুচিত buckets (গতিশীল আকার) ব্যবহার করা হয়
  2. পূর্বনির্ধারিত ডেটা সহ আরও ভাল কম্প্রেশন ফ্যাক্টর অর্জন করা সহজ, সুতরাং প্রতিটি বালতির জন্য স্ট্যাটিক বাফার রয়েছে (বাফারের সংখ্যাগুলি LZMA এর আগে সাজানো হবে)
  3. প্রতিটি বালতি একটি নির্দিষ্ট পরিসীমা ধারণ করে, তাই চূড়ান্ত সাজানোর প্রতিটি বালতি আলাদাভাবে জন্য করা যেতে পারে
  4. বাকেটের আকার সঠিকভাবে সেট করা যেতে পারে, তাই সঞ্চয়কৃত ডেটা ডিমপ্রেস করার জন্য পর্যাপ্ত মেমরি থাকবে এবং প্রতিটি বালতি আলাদাভাবে চূড়ান্তভাবে সাজানো হবে

দয়া করে নোট করুন, সংযুক্ত কোডটি একটি POC , এটি একটি চূড়ান্ত সমাধান হিসাবে ব্যবহার করা যাবে না, এটি পূর্বনির্ধারিত ভাবে (সম্ভাব্য সংকুচিত) কোনও সংখ্যক ছোট বাফারগুলি ব্যবহার করার জন্য পূর্বনির্ধারিত সংখ্যাকে সংরক্ষণ করার ধারণাটি প্রদর্শন করে। LZMA একটি চূড়ান্ত সমাধান হিসাবে প্রস্তাব করা হয় না। এটি এই পোকে কম্প্রেশন পরিচয় করানোর দ্রুততম সম্ভাব্য উপায় হিসাবে ব্যবহার করা হয়।

নীচের পিওসি কোডটি দেখুন (এটি কেবলমাত্র একটি ডেমো নোট করুন, এটি কম্পাইল করার জন্য LZMA-Java প্রয়োজন হবে):

public class MemorySortDemo {

static final int NUM_COUNT = 1000000;
static final int NUM_MAX   = 100000000;

static final int BUCKETS      = 5;
static final int DICT_SIZE    = 16 * 1024; // LZMA dictionary size
static final int BUCKET_SIZE  = 1024;
static final int BUFFER_SIZE  = 10 * 1024;
static final int BUCKET_RANGE = NUM_MAX / BUCKETS;

static class Producer {
    private Random random = new Random();
    public int produce() { return random.nextInt(NUM_MAX); }
}

static class Bucket {
    public int size, pointer;
    public int[] buffer = new int[BUFFER_SIZE];

    public ByteArrayOutputStream tempOut = new ByteArrayOutputStream();
    public DataOutputStream tempDataOut = new DataOutputStream(tempOut);
    public ByteArrayOutputStream compressedOut = new ByteArrayOutputStream();

    public void submitBuffer() throws IOException {
        Arrays.sort(buffer, 0, pointer);

        for (int j = 0; j < pointer; j++) {
            tempDataOut.writeInt(buffer[j]);
            size++;
        }            
        pointer = 0;
    }

    public void write(int value) throws IOException {
        if (isBufferFull()) {
            submitBuffer();
        }
        buffer[pointer++] = value;
    }

    public boolean isBufferFull() {
        return pointer == BUFFER_SIZE;
    }

    public byte[] compressData() throws IOException {
        tempDataOut.close();
        return compress(tempOut.toByteArray());
    }        

    private byte[] compress(byte[] input) throws IOException {
        final BufferedInputStream in = new BufferedInputStream(new ByteArrayInputStream(input));
        final DataOutputStream out = new DataOutputStream(new BufferedOutputStream(compressedOut));

        final Encoder encoder = new Encoder();
        encoder.setEndMarkerMode(true);
        encoder.setNumFastBytes(0x20);
        encoder.setDictionarySize(DICT_SIZE);
        encoder.setMatchFinder(Encoder.EMatchFinderTypeBT4);

        ByteArrayOutputStream encoderPrperties = new ByteArrayOutputStream();
        encoder.writeCoderProperties(encoderPrperties);
        encoderPrperties.flush();
        encoderPrperties.close();

        encoder.code(in, out, -1, -1, null);
        out.flush();
        out.close();
        in.close();

        return encoderPrperties.toByteArray();
    }

    public int[] decompress(byte[] properties) throws IOException {
        InputStream in = new ByteArrayInputStream(compressedOut.toByteArray());
        ByteArrayOutputStream data = new ByteArrayOutputStream(10 * 1024);
        BufferedOutputStream out = new BufferedOutputStream(data);

        Decoder decoder = new Decoder();
        decoder.setDecoderProperties(properties);
        decoder.code(in, out, 4 * size);

        out.flush();
        out.close();
        in.close();

        DataInputStream input = new DataInputStream(new ByteArrayInputStream(data.toByteArray()));
        int[] array = new int[size];
        for (int k = 0; k < size; k++) {
            array[k] = input.readInt();
        }

        return array;
    }
}

static class Sorter {
    private Bucket[] bucket = new Bucket[BUCKETS];

    public void doSort(Producer p, Consumer c) throws IOException {

        for (int i = 0; i < bucket.length; i++) {  // allocate buckets
            bucket[i] = new Bucket();
        }

        for(int i=0; i< NUM_COUNT; i++) {         // produce some data
            int value = p.produce();
            int bucketId = value/BUCKET_RANGE;
            bucket[bucketId].write(value);
            c.register(value);
        }

        for (int i = 0; i < bucket.length; i++) { // submit non-empty buffers
            bucket[i].submitBuffer();
        }

        byte[] compressProperties = null;
        for (int i = 0; i < bucket.length; i++) { // compress the data
            compressProperties = bucket[i].compressData();
        }

        printStatistics();

        for (int i = 0; i < bucket.length; i++) { // decode & sort buckets one by one
            int[] array = bucket[i].decompress(compressProperties);
            Arrays.sort(array);

            for(int v : array) {
                c.consume(v);
            }
        }
        c.finalCheck();
    }

    public void printStatistics() {
        int size = 0;
        int sizeCompressed = 0;

        for (int i = 0; i < BUCKETS; i++) {
            int bucketSize = 4*bucket[i].size;
            size += bucketSize;
            sizeCompressed += bucket[i].compressedOut.size();

            System.out.println("  bucket[" + i
                    + "] contains: " + bucket[i].size
                    + " numbers, compressed size: " + bucket[i].compressedOut.size()
                    + String.format(" compression factor: %.2f", ((double)bucket[i].compressedOut.size())/bucketSize));
        }

        System.out.println(String.format("Data size: %.2fM",(double)size/(1014*1024))
                + String.format(" compressed %.2fM",(double)sizeCompressed/(1014*1024))
                + String.format(" compression factor %.2f",(double)sizeCompressed/size));
    }
}

static class Consumer {
    private Set<Integer> values = new HashSet<>();

    int v = -1;
    public void consume(int value) {
        if(v < 0) v = value;

        if(v > value) {
            throw new IllegalArgumentException("Current value is greater than previous: " + v + " > " + value);
        }else{
            v = value;
            values.remove(value);
        }
    }

    public void register(int value) {
        values.add(value);
    }

    public void finalCheck() {
        System.out.println(values.size() > 0 ? "NOT OK: " + values.size() : "OK!");
    }
}

public static void main(String[] args) throws IOException {
    Producer p = new Producer();
    Consumer c = new Consumer();
    Sorter sorter = new Sorter();

    sorter.doSort(p, c);
}
}

র্যান্ডম সংখ্যা সঙ্গে এটি নিম্নলিখিত উত্পাদন করে:

bucket[0] contains: 200357 numbers, compressed size: 353679 compression factor: 0.44
bucket[1] contains: 199465 numbers, compressed size: 352127 compression factor: 0.44
bucket[2] contains: 199682 numbers, compressed size: 352464 compression factor: 0.44
bucket[3] contains: 199949 numbers, compressed size: 352947 compression factor: 0.44
bucket[4] contains: 200547 numbers, compressed size: 353914 compression factor: 0.44
Data size: 3.85M compressed 1.70M compression factor 0.44

একটি সহজ আরোহী ক্রম জন্য (এক বালতি ব্যবহৃত হয়) এটি উত্পাদিত:

bucket[0] contains: 1000000 numbers, compressed size: 256700 compression factor: 0.06
Data size: 3.85M compressed 0.25M compression factor 0.06

সম্পাদনা

উপসংহার:

  1. Nature বোকা করার চেষ্টা করবেন না
  2. নিম্ন মেমরি পদচিহ্ন সঙ্গে সহজ সংকোচ ব্যবহার করুন
  3. কিছু অতিরিক্ত সূত্র সত্যিই প্রয়োজন হয়। সাধারণ বুলেট-প্রমাণ সমাধান কার্যকরী বলে মনে হচ্ছে না।

পর্যায় 2: উন্নত কম্প্রেশন, চূড়ান্ত উপসংহার

আগের বিভাগে ইতিমধ্যে উল্লেখ করা হয়েছে, কোন উপযুক্ত কম্প্রেশন কৌশল ব্যবহার করা যেতে পারে। সুতরাং সহজ এবং ভাল (সম্ভব হলে) পদ্ধতির পক্ষে LZMA পরিত্রাণ পেতে। এরিথমেটিক কোডিং , র্যাডিক্স ট্রি ইত্যাদি সহ অনেক ভাল সমাধান রয়েছে।

যাইহোক, সহজ কিন্তু কার্যকর এনকোডিং প্রকল্পটি অন্য বহিরাগত লাইব্রেরির তুলনায় আরো চিত্রশালী হবে, কিছু নিফটি অ্যালগরিদম প্রদান করবে। প্রকৃত সমাধানটি খুব সোজা: কারণ আংশিকভাবে সাজানো ডেটা সহ buckets আছে, সংখ্যাগুলির পরিবর্তে ডেল্টাস ব্যবহার করা যেতে পারে।

র্যান্ডম ইনপুট পরীক্ষা সামান্য ভাল ফলাফল দেখায়:

bucket[0] contains: 10103 numbers, compressed size: 13683 compression factor: 0.34
bucket[1] contains: 9885 numbers, compressed size: 13479 compression factor: 0.34
...
bucket[98] contains: 10026 numbers, compressed size: 13612 compression factor: 0.34
bucket[99] contains: 10058 numbers, compressed size: 13701 compression factor: 0.34
Data size: 3.85M compressed 1.31M compression factor 0.34

কোডের উদাহরণ

  public static void encode(int[] buffer, int length, BinaryOut output) {
    short size = (short)(length & 0x7FFF);

    output.write(size);
    output.write(buffer[0]);

    for(int i=1; i< size; i++) {
        int next = buffer[i] - buffer[i-1];
        int bits = getBinarySize(next);

        int len = bits;

        if(bits > 24) {
          output.write(3, 2);
          len = bits - 24;
        }else if(bits > 16) {
          output.write(2, 2);
          len = bits-16;
        }else if(bits > 8) {
          output.write(1, 2);
          len = bits - 8;
        }else{
          output.write(0, 2);
        }

        if (len > 0) {
            if ((len % 2) > 0) {
                len = len / 2;
                output.write(len, 2);
                output.write(false);
            } else {
                len = len / 2 - 1;
                output.write(len, 2);
            }

            output.write(next, bits);
        }
    }
}

public static short decode(BinaryIn input, int[] buffer, int offset) {
    short length = input.readShort();
    int value = input.readInt();
    buffer[offset] = value;

    for (int i = 1; i < length; i++) {
        int flag = input.readInt(2);

        int bits;
        int next = 0;
        switch (flag) {
            case 0:
                bits = 2 * input.readInt(2) + 2;
                next = input.readInt(bits);
                break;
            case 1:
                bits = 8 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
            case 2:
                bits = 16 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
            case 3:
                bits = 24 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
        }

        buffer[offset + i] = buffer[offset + i - 1] + next;
    }

   return length;
}

অনুগ্রহ করে মনে রাখবেন, এই পদ্ধতির:

  1. মেমরি অনেক গ্রাস না
  2. স্ট্রিম সঙ্গে কাজ করে
  3. তাই খারাপ ফলাফল প্রদান করে না

সম্পূর্ণ কোড here পাওয়া here , বাইনারি ইনপুট এবং বাইনারি আউটপুট বাস্তবায়ন here পাওয়া here

চূড়ান্ত উপসংহার

কোন চূড়ান্ত সিদ্ধান্ত নেই :) কখনও কখনও একটি স্তর স্তর সরানো এবং একটি meta-level বিন্দু দৃষ্টিকোণ থেকে টাস্ক পর্যালোচনা করার সত্যিই ভাল ধারণা।

এটা এই কাজের সঙ্গে কিছু সময় ব্যয় মজা ছিল। BTW, নীচের আকর্ষণীয় উত্তর অনেক আছে। আপনার মনোযোগ এবং শুভ codding জন্য আপনাকে ধন্যবাদ।


Answer #19

আমি সমাধান ভিডিও এনকোডিং, যেমন বিচ্ছিন্ন কোসাইন রূপান্তর থেকে কৌশল একত্রিত মনে হয়। ডিজিটাল ভিডিওতে, 110 112 115 116 হিসাবে নিয়মিত মান হিসাবে ভিডিওটির উজ্জ্বলতা বা রঙ পরিবর্তন করার রেকর্ডিং করা হয়, প্রতিটিটি শেষের (রান দৈর্ঘ্যের এনকোডিংয়ের মতো) থেকে বিয়োগ করা হয়। 110 112 115 116 110 2 3 হয়ে যায়। মানগুলি, 3 3 1 এর চেয়ে কম বিট দরকার।

সুতরাং আসুন আমরা সকেটে পৌঁছাতে ইনপুট মানগুলির একটি তালিকা তৈরি করি। আমরা প্রতিটি উপাদান, মান না, কিন্তু পূর্বে এটি অফসেট সংরক্ষণ করা হয়। আমরা যেতে হিসাবে আমরা সাজানোর, তাই অফসেট শুধুমাত্র ইতিবাচক হতে যাচ্ছে। কিন্তু অফসেট 8 দশমিক ডিজিটের প্রশস্ত হতে পারে যা এটি 3 বাইটে ফিট করে। প্রতিটি উপাদান 3 বাইট হতে পারে না, তাই আমরা এই প্যাক প্রয়োজন। আমরা প্রতিটি বাইটের শীর্ষ বিটকে "অবিরত বিট" হিসাবে ব্যবহার করতে পারি, যা নির্দেশ করে যে পরবর্তী বাইট সংখ্যাটির অংশ এবং প্রতিটি বাইটের নিম্ন 7 বিটগুলি একত্রিত করার প্রয়োজন। শূন্য সদৃশ জন্য বৈধ।

তালিকাটি পূরণ হয়ে গেলে, সংখ্যাগুলি একসাথে ঘনিষ্ঠ হওয়া উচিত, যার অর্থ হল কেবলমাত্র 1 বাইট গড় মূল্যের দূরত্ব নির্ধারণ করতে ব্যবহৃত হয়। 7 বিট মান এবং 1 বিট অফসেট সুবিধাজনক থাকলে, কিন্তু একটি মিষ্টি স্পট থাকতে পারে যার জন্য একটি "অবিরত" মানের জন্য 8 বিট কম।

যাই হোক, আমি কিছু পরীক্ষা করেছি। আমি একটি এলোমেলো সংখ্যা জেনারেটর ব্যবহার করি এবং আমি প্রায় 1২79000 বাইটে 8 মিলিয়নের দশমিক দশমিক সংখ্যা সংশোধন করতে পারি। প্রতিটি সংখ্যা মধ্যে গড় স্থান ধারাবাহিকভাবে 99 ...

public class Test {
    public static void main(String[] args) throws IOException {
        // 1 million values
        int[] values = new int[1000000];

        // create random values up to 8 digits lrong
        Random random = new Random();
        for (int x=0;x<values.length;x++) {
            values[x] = random.nextInt(100000000);
        }
        Arrays.sort(values);

        ByteArrayOutputStream baos = new ByteArrayOutputStream();

        int av = 0;    
        writeCompact(baos, values[0]);     // first value
        for (int x=1;x<values.length;x++) {
            int v = values[x] - values[x-1];  // difference
            av += v;
            System.out.println(values[x] + " diff " + v);
            writeCompact(baos, v);
        }

        System.out.println("Average offset " + (av/values.length));
        System.out.println("Fits in " + baos.toByteArray().length);
    }

    public static void writeCompact(OutputStream os, long value) throws IOException {
        do {
            int b = (int) value & 0x7f;
            value = (value & 0x7fffffffffffffffl) >> 7;
            os.write(value == 0 ? b : (b | 0x80));
        } while (value != 0);
    }
}

Answer #20

এখন একটি প্রকৃত সমাধান লক্ষ্য করা, 8 ডিজিটের সীমাতে ইনপুট এর সম্ভাব্য সমস্ত ক্ষেত্রেই কেবলমাত্র 1 এমবি র্যাম রয়েছে। উল্লেখ্য: অগ্রগতি কাজ, আগামীকাল চলতে থাকবে। সাজানো ইটগুলির ডেল্টাসের গাণিতিক কোডিং ব্যবহার করে, 1 এম সাজানো ইটের জন্য সবচেয়ে খারাপ ক্ষেত্রে প্রায় 7 বিট খরচ হবে (99 999999/1000000 99 টি এবং লগ 2 (99) প্রায় 7 বিট)।

কিন্তু আপনার 7 ম 8 ইন্টিগ্রারের দরকার 7 বা 8 বিট পেতে! সংক্ষিপ্ত সিরিজ বৃহত্তর deltas হবে, তাই উপাদান প্রতি আরো বিট।

আমি যতটা সম্ভব সম্ভব এবং সংকুচিত (প্রায়) জায়গায় গ্রহণ করতে কাজ করছি। ২50 কেজি ইটের প্রথম ব্যাচের প্রতিটিতে প্রায় 9 বিট দরকার। ফলে ফলাফল প্রায় 275 কেবি নিতে হবে। অবশিষ্ট বিনামূল্যে মেমরি কয়েক বার সঙ্গে পুনরাবৃত্তি করুন। তারপর decompress- একত্রিত-জায়গায়-সংকুচিত অংশ সংকুচিত। এটি বেশ কঠিন , কিন্তু সম্ভব। আমি মনে করি.

মার্জ তালিকা পূর্ণসংখ্যা টার্গেট প্রতি 7bit কাছাকাছি এবং কাছাকাছি পেতে হবে। কিন্তু আমি জানি না মার্জ লুপ কতটা পুনরাবৃত্তি করবে। সম্ভবত 3।

কিন্তু গাণিতিক কোডিং বাস্তবায়ন অনির্ধারণ এটি অসম্ভব হতে পারে। এই সমস্যাটি যদি সম্ভব হয় তবে এটি অত্যন্ত টাইট হবে।

কোন স্বেচ্ছাসেবক?


Answer #21

কৌতুকটি আলগোরিদিম স্টেটকে প্রতিনিধিত্ব করা, যা একটি পূর্ণসংখ্যা মাল্টি সেট, "বৃদ্ধি কাউন্টার" = "+" এবং "আউটপুট কাউন্টার" = "!" এর সংকুচিত স্ট্রিম হিসাবে। অক্ষর। উদাহরণস্বরূপ, সেটটি {0,3,3,4} "+++ !! !!!" হিসাবে উপস্থাপিত হবে, যেকোনো সংখ্যক "+" অক্ষর অনুসরণ করে। মাল্টি-সেট সংশোধন করতে আপনি অক্ষরগুলি স্ট্রিম করুন, কেবলমাত্র একটি ধ্রুবক পরিমাণকে একযোগে ডিকম্প্রেস করে রাখুন এবং সংকোচিত ফর্মটিতে তাদের স্ট্রিমিং করার আগে স্থান পরিবর্তন করুন।

বিস্তারিত

আমরা চূড়ান্ত সেটের মধ্যে ঠিক 10 ^ 6 সংখ্যা জানি, তাই সর্বাধিক 10 ^ 6 "!" অক্ষর। আমরাও জানি যে আমাদের পরিসরের আকার 10 ^ 8, যার অর্থ সর্বাধিক 10 ^ 8 "+" অক্ষর রয়েছে। আমরা 10 ^ 8 "+" গুলি মধ্যে 10 ^ 6 "!" এর ব্যবস্থা করতে পারব এমন উপায়গুলির সংখ্যা (10^8 + 10^6) choose 10^6, এবং নির্দিষ্ট কিছু ব্যবস্থা নির্দিষ্ট করে ~ 0.965 MiB এর তথ্য গ্রহণ করে। যে একটি টাইট হইয়া হবে।

আমরা আমাদের কোটা অতিক্রম ছাড়া স্বাধীন প্রতিটি অক্ষর আচরণ করতে পারেন। "100" এর চেয়ে 100 গুণ বেশি অক্ষর আছে!! অক্ষর, যা 100 এ সরল করে: প্রতিটি চরিত্রের 1 টি বিজোড় "+" হচ্ছে যদি আমরা ভুলে যাই যে তারা নির্ভরশীল। 100: 101 এর বিজোড় প্রতি ~ 0.08 বিট প্রতি চরিত্রের অনুরূপ, প্রায় ~ 0.965 MiB (নির্ভরতা উপেক্ষা করে এই ক্ষেত্রে শুধুমাত্র ~ 12 বিট খরচ !) রয়েছে।

পূর্বে পরিচিত সম্ভাবনা সঙ্গে স্বাধীন অক্ষর সংরক্ষণের জন্য সহজ পদ্ধতি হাফম্যান কোডিং হয় । উল্লেখ্য, আমাদের একটি অকপট বড় গাছের প্রয়োজন (10 অক্ষরের ব্লকগুলির জন্য একটি হাফম্যান ট্রি প্রায় ২.4 বিট প্রতি ব্লকের গড় খরচ, মোট 2.9 9 মিব। ২0 অক্ষরের ব্লকগুলির জন্য একটি হাফম্যান ট্রি রয়েছে প্রতি ব্লক গড় খরচ প্রায় 3 বিট যা মোট ~ 1.8 মিবি। আমরা সম্ভবত শতকের ক্রম অনুসারে আকারের একটি ব্লকের প্রয়োজন বোধ করি, যা আমাদের অস্তিত্বের সমস্ত কম্পিউটার সরঞ্জামের চেয়ে আমাদের গাছের আরো নোড বোঝাতে পারে। )। যাইহোক, রম টেকনিক্যালি "মুক্ত" সমস্যা এবং ব্যবহারিক সমাধান অনুসারে গাছের নিয়মিততার সুবিধা গ্রহণ করে তা অবশ্যই একই রকম দেখাবে।

ছদ্ম-কোড

  • রোমে সংরক্ষিত যথেষ্ট হাফম্যান গাছ (অথবা একই ব্লক-বাই-ব্লক কম্প্রেশন ডেটা) আছে
  • 10 ^ 8 "+" অক্ষরের সংকুচিত স্ট্রিং দিয়ে শুরু করুন।
  • N নম্বরটি সন্নিবেশ করানোর জন্য, এন "+" অক্ষর অতীত চলে যাওয়ার আগে সংকুচিত স্ট্রিংটি স্ট্রিম করুন তারপর একটি "!" সন্নিবেশ করান। পূর্ববর্তী একের উপর পুনরায় কম্প্রেসড স্ট্রিংটি স্ট্রিম করুন, যেমন আপনি যেতে চান, বাফার ব্লকগুলির স্থির পরিমাণে / কম-রানগুলি এড়ানোর জন্য।
  • এক মিলিয়ন বার পুনরাবৃত্তি করুন: [ইনপুট, স্ট্রীম ডিকম্প্রেস> সন্নিবেশ> কম্প্রেস], তারপর আউটপুট ডিকম্প্রেস করুন

Answer #22

এ পর্যন্ত এখানে উল্লিখিত একটি চটচটে কৌশল আছে। আমরা অনুমান করি যে আপনার কাছে ডেটা সংরক্ষণ করার কোন অতিরিক্ত উপায় নেই, তবে এটি কঠোরভাবে সত্য নয়।

আপনার সমস্যার চারপাশে একটি উপায় হল নিম্নলিখিত ভয়ঙ্কর জিনিসটি, যে কোনও পরিস্থিতিতে যে কোনও ব্যক্তির দ্বারা চেষ্টা করা উচিত নয়: তথ্য সঞ্চয় করতে নেটওয়ার্ক ট্র্যাফিক ব্যবহার করুন। এবং না, আমি নাশ মানে না।

নিম্নলিখিত সংখ্যায় আপনি কয়েকটি বাইট RAM দ্বারা সংখ্যার ক্রম দিতে পারেন:

  • প্রথমে ২ টি ভেরিয়েবল নিন: COUNTER এবং VALUE
  • প্রথম সব নিবন্ধন 0 সেট করুন;
  • প্রতিবার আপনি যখন পূর্ণসংখ্যা পাবেন, COUNTER বৃদ্ধি করুন এবং VALUE সেটিকে max(VALUE, I) ;
  • তারপর রাউটারে ডেটা সেট করে একটি ICMP ইকো অনুরোধ প্যাকেট পাঠান। আমি মুছে ফেলা এবং পুনরাবৃত্তি।
  • প্রতিবার যখন আপনি ফেরত ICMP প্যাকেটটি পান তখন আপনি কেবল পূর্ণসংখ্যাটি সরাতে এবং অন্য ইকো অনুরোধে আবার এটি পাঠান। এটি আইসিএমপি অনুরোধগুলির একটি বড় সংখ্যা উৎপন্ন করে যা পূর্ববর্তী এবং ফন্টগুলিকে পূর্ণসংখ্যা ধারণ করে।

একবার COUNTER 1000000 পৌঁছে গেলে, আপনার ICMP অনুরোধগুলি অবিরাম প্রবাহে সংরক্ষিত সমস্ত মান রয়েছে এবং VALUE এখন সর্বোচ্চ পূর্ণসংখ্যা রয়েছে। কিছু threshold T >> 1000000 । শূন্য থেকে COUNTER সেট করুন। প্রতিবার যখন আপনি একটি ICMP প্যাকেট পাবেন, COUNTER বৃদ্ধি করবেন এবং অন্তর্ভুক্ত ইন্টিগ্রারটি অন্য ইকো অনুরোধে ফেরত পাঠান, যতক্ষণ না I=VALUE , সাজানো পূর্ণসংখ্যাগুলির জন্য গন্তব্যে প্রেরণ করি। একবার COUNTER=T , হ্রাস VALUE দ্বারা 1 , COUNTER শূন্যতে পুনরায় সেট করুন এবং পুনরাবৃত্তি করুন। একবার VALUE শূন্য পৌঁছে গেলে আপনি সর্বনিম্ন থেকে ক্ষুদ্রতম গন্তব্য পর্যন্ত সমস্ত পূর্ণসংখ্যা প্রেরণ করেছেন এবং দুটি স্থায়ী ভেরিয়েবলগুলির জন্য শুধুমাত্র 47 বিট RAM ব্যবহার করেছেন (এবং সাময়িক মানগুলির জন্য আপনার যেকোন ছোট পরিমাণের প্রয়োজন)।

আমি জানি এটি ভয়ানক, এবং আমি জানি যে সব ধরনের বাস্তব সমস্যা থাকতে পারে, কিন্তু আমি মনে করি এটি আপনার কিছু হাসতে পারে বা অন্তত আপনাকে ভীত করে।


Answer #23

সমস্ত সম্ভাব্য ইনপুট জুড়ে এই সমস্যার সমাধান। প্রতারণা।

  1. টিসিপি থেকে এম মানগুলি পড়ুন, যেখানে মি সর্বোচ্চ মানের কাছে যা মেমরিতে সাজানো যেতে পারে, সম্ভবত n / 4।
  2. 250,000 (বা তাই) সংখ্যা বাছাই এবং তাদের আউটপুট।
  3. অন্যান্য 3 চতুর্থাংশের জন্য পুনরাবৃত্তি করুন।
  4. রিসিভারটি সংখ্যাগুলির 4 টি তালিকাকে একত্রিত করতে দেয় যেহেতু এটি তাদের প্রক্রিয়া হিসাবে গ্রহণ করেছে। (এটি একটি তালিকা ব্যবহার করার চেয়ে অনেক ধীর।)

Answer #24

(আমার মূল উত্তর ভুল ছিল, খারাপ গণিতের জন্য দুঃখিত, বিরতির নিচে দেখুন।)

কিভাবে এই সম্পর্কে?

প্রথম 27 বিটগুলি আপনার সর্বনিম্ন নম্বরটি সঞ্চয় করে, তারপর পরবর্তী সংখ্যাটিতে পার্থক্যটি নিম্নরূপ এনকোড করা হয়েছে: 5 বিট পার্থক্য সঞ্চয় করতে ব্যবহৃত বিটগুলির সংখ্যা সংরক্ষণ করার জন্য, তারপর পার্থক্য। আপনি যে সংখ্যা আবার দেখেছেন তা নির্দেশ করতে 00000 ব্যবহার করুন।

এটি কাজ করে কারণ আরো সংখ্যক সংখ্যার সন্নিবেশ করা হয়েছে, সংখ্যাগুলির মধ্যে গড় পার্থক্য হ্রাস পেয়েছে, তাই আপনি আরও সংখ্যক সংখ্যার যোগ হিসাবে পার্থক্য সঞ্চয় করতে কম বিট ব্যবহার করেন। আমি বিশ্বাস করি এই একটি ডেল্টা তালিকা বলা হয়।

সবচেয়ে খারাপ ক্ষেত্রে আমি মনে করতে পারি যে সব সংখ্যা সমানভাবে (100 দ্বারা), উদাহরণস্বরূপ Assuming 0 হল প্রথম সংখ্যা:

000000000000000000000000000 00111 1100100
                            ^^^^^^^^^^^^^
                            a million times

27 + 1,000,000 * (5+7) bits = ~ 427k

রেডডিট উদ্ধার!

আপনি যদি তাদের সব ছিল সাজানোর ছিল, এই সমস্যা সহজ হবে। আপনি যে সংখ্যাগুলি দেখেছেন তা সঞ্চয় করতে 1২2k (1 মিলিয়ন বিট) লাগে (যদি 0 টি 0 বিট দেখানো হয়, ২300 বিট 2300 দেখানো হয়, ইত্যাদি।)

আপনি সংখ্যা পড়া, বিট ক্ষেত্রে তাদের সংরক্ষণ করুন, এবং তারপর গণনা পালন করে বিট পাল্টা।

কিন্তু, আপনি কত আপনি দেখেছেন মনে আছে। আমি এই প্রকল্পের সাথে উত্থাপিত উপরে sublist উত্তর দ্বারা অনুপ্রাণিত ছিল:

এক বিট ব্যবহার করার পরিবর্তে, 2 বা 27 বিট ব্যবহার করুন:

  • 00 মানে আপনি সংখ্যা দেখতে না।
  • 01 মানে আপনি একবার দেখেছেন
  • 1 মানে আপনি এটি দেখেছেন, এবং পরবর্তী 26 বিট কতবার কতবার গণনা করা হয়।

আমার মনে হয় এটি কাজ করে: যদি কোন সদৃশ থাকে তবে আপনার একটি 244k তালিকা রয়েছে। সবচেয়ে খারাপ ক্ষেত্রে আপনি দুইবার প্রতিটি নম্বর দেখতে পান (যদি আপনি এক নম্বর তিনটি সংখ্যা দেখেন তবে এটি আপনার জন্য বাকি তালিকাটি সংক্ষিপ্ত করে), এর অর্থ আপনি একবারে 50,000 টি দেখেছেন এবং আপনি 950,000 টি আইটেম 0 বা 1 বার দেখেছেন।

50,000 * 27 + 950,000 * 2 = 396.7 কে।

আপনি নিম্নলিখিত এনকোডিং ব্যবহার করলে আরও উন্নতি করতে পারেন:

0 এর মানে হল আপনি 10 নম্বরটি দেখতে পান নি তা একবার দেখেছেন 11 আপনি কীভাবে গণনা করেন

যা, গড়, ফলে 280.7k স্টোরেজ ফলাফল হবে।

সম্পাদনা করুন: আমার রবিবার সকালে গণিত ভুল ছিল।

সবচেয়ে খারাপ ক্ষেত্রে আমরা 500,000 সংখ্যা দুবার দেখতে পাই, তাই গণিতটি হয়ে যায়:

500,000 * 27 + 500,000 * ২ = 1.77 মি

বিকল্প এনকোডিং একটি গড় স্টোরেজ ফলাফল

500,000 * 27 + 500,000 = 1.70 মি

: (





ram