टीएल;डीआर
- समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
- दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ५.८: एकरंगी स्क्रीन बाइट सरणी में, हर बाइट में आठ पिक्सेल। (x१, y) से (x२, y) तक क्षैतिज रेखा: आंशिक बाइट पर बिट मास्क, पूरे बाइट पर ०एक्सएफएफ।
- जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।
सस्ती पुरानी स्क्रीन में रंग नहीं। हर पिक्सेल या तो जलता है या बुझा। याददाश्त कम है, इसलिए हार्डवेयर आठ पिक्सेल एक बाइट में ठूँसता है। तुम्हें सपाट byte[] और चौड़ाई मिलती है। काम: एक क्षैतिज रेखा पर हर पिक्सेल जलाओ, स्तंभ x1 से x2 तक, पंक्ति y पर। बीच में पूरे बाइट बैठे हों तो हर बिट पर अलग लूप मत घुमाओ।
यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली बिट-बफर ड्राइंग समस्या का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ५, बिट हेरफेर, यहीं खत्म होता है।
१. रोज़मर्रा की उपमा
लंबी दीवार पर स्विच की कतार सोचो। स्विच आठ-आठ के गुट में आते हैं: हर गुट एक प्लास्टिक पट्टी, एक बाइट। स्विच ऑन करो, वह पिक्सेल जलता है।
एक शेल्फ (पंक्ति y) पर स्विच x1 से x2 तक सीधी क्षैतिज पट्टी चाहिए।
अगर पट्टी छोटी है और एक ही गुट में समाती है, तो उसी पट्टी के चुने स्विच पलटो। अगर लंबी है, तो बीच के पूरे गुट एक साथ जलते हैं: पूरी पट्टी एक झटके में (0xFF)। सिर्फ पहली और आखिरी पट्टी पर सावधानी से आंशिक पलट। पूरी बात यही है।
२. समस्या सादे शब्दों में
इनपुट:
byte[] screen: पैक एकरंगी फ्रेमबफर। बिट1मतलब पिक्सेल जलता,0बुझा।int width: स्क्रीन की चौड़ाई पिक्सेल में। ८ से विभाज्य गारंटी, इसलिए कोई पंक्ति बाइट को दो पंक्तियों में नहीं तोड़ती।int x1,int x2: रेखा के शुरू और अंत स्तंभ (समावेशी)।int y: पंक्ति सूचकांक।
आउटपुट: screen बदलो ताकि (x1, y) से (x2, y) तक हर पिक्सेल जल जाए। बाकी जैसे थे वैसे रहें (आंशिक बाइट पर OR करो, अंधा ओवरराइट नहीं)।
लेआउट (बाएँ एमएसबी):
- प्रति पंक्ति बाइट:
width / 8। - पिक्सेल
(x, y)का बाइट सूचकांक:(width / 8) * y + (x / 8)। - उस बाइट में बिट: ऑफसेट
x % 8बिट(7 - (x % 8))पर। बाइट का सबसे बायाँ पिक्सेल ऊँचा बिट।
सिग्नेचर का आकार:
void drawLine(byte[] screen, int width, int x1, int x2, int y)
छोटा उदाहरण: चौड़ाई 16 (प्रति पंक्ति दो बाइट)। y = 0 पर x1 = 3 से x2 = 12।
byte 0 of row 0 byte 1 of row 0
pixels 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
bits 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
before: 00000000 00000000
after: 00011111 11111000
^^^start mask end mask^^^
full run in the middle is just those bits; no full middle byte here
अगर रेखा लंबी हो और तीन या ज़्यादा बाइट स्तंभ काटे, तो बीच के स्तंभ एक-एक लिखत में 0xFF हो जाते।
कोड से पहले स्पष्ट करो:
- क्या
x1औरx2समावेशी हैं? (हाँ।) - अगर
x1 > x2? (अदला-बदली, या खाली। इंटरव्यू में अदला-बदली आमतौर पर चलती है।) - बाएँ एमएसबी या एलएसबी? (अपना नियम बताओ। यहाँ एमएसबी = बायाँ पिक्सेल।)
- क्या ड्रॉ दूसरे पिक्सेल मिटाए? (नहीं। किनारों पर
|=।) - क्या चौड़ाई हमेशा ८ की गुणज? (क्लासिक कथन में हाँ।)
३. पहले सोचो
सीधा: एक-एक पिक्सेल
for x from x1 to x2:
setBit(screen, width, x, y)
setBit बाइट ढूँढ़ता है, एक-बिट मास्क बनाता है, OR करता है। सही। सरल। लंबाई L की रेखा पर L बिट छूते हो। छोटी रेखाओं के लिए ठीक। जब L हजारों हो और ज़्यादातर बिट बीच के पूरे बाइट में हों, तब बेकार।
बेहतर: पूरे बाइट + किनारे के मास्क
पंक्ति y पर x1 और x2 के बाइट स्तंभ निकालो।
१. शुरुआती आंशिक बाइट: शुरू ऑफसेट से उस बाइट के अंत तक मास्क।
२. बीच के पूरे बाइट: शुरू और अंत के सख्त बीच हर पूरा बाइट 0xFF (या |= 0xFF)।
३. आखिरी आंशिक बाइट: उस बाइट की शुरुआत से अंत ऑफसेट तक मास्क।
४. एक ही बाइट का केस: जब x1 और x2 एक बाइट साझा करें, शुरू और अंत मास्क का AND, एक बार लगाओ। पूरे-बाइट वाला रास्ता मत चलाओ, नहीं तो रेंज बिगड़ेगी।
ऑफसेट:
startOffset = x1 % 8
endOffset = x2 % 8
startByte = x1 / 8
endByte = x2 / 8
शुरुआती मास्क (startOffset से बाइट के अंत तक जलाना):
startMask = 0xFF >>> startOffset
// startOffset 0 -> 11111111
// startOffset 3 -> 00011111
अंत मास्क (पैकिंग की शुरुआत से endOffset तक):
endMask = 0xFF << (7 - endOffset) // फिर निचले ८ बिट रखो
// endOffset 0 -> 10000000
// endOffset 3 -> 11110000
// endOffset 7 -> 11111111
पहले और आखिरी पूरे बाइट का सूचकांक:
- अगर रेखा बाइट के बीच से शुरू हो, पहला पूरा बाइट
startByte + 1। - अगर अंत बीच में हो (बाइट के आखिरी बिट पर नहीं), आखिरी पूरा बाइट
endByte - 1। - अगर पहला-पूरा सूचकांक आखिरी-पूरे से बड़ा हो, बीच में कोई पूरा बाइट नहीं। छोटी रेखाएँ और एक-बाइट केस यहीं आते हैं।
स्क्रीन की ऊँचाई screen.length / (width / 8)। अगर y भरोसेमंद रेंज में है तो अक्सर ज़रूरत नहीं।
४. जावा हल
सहायक (वैकल्पिक, साफ)
/** Bytes in one scanline. width is in pixels and divisible by 8. */
static int bytesPerRow(int width) {
return width / 8;
}
static int byteIndex(int width, int x, int y) {
return bytesPerRow(width) * y + (x / 8);
}
मुख्य: मास्क + पूरे बाइट
void drawLine(byte[] screen, int width, int x1, int x2, int y) {
if (screen == null || width <= 0 || (width % 8) != 0) {
return;
}
if (x1 > x2) {
int t = x1;
x1 = x2;
x2 = t;
}
// optional: clamp or reject out-of-range x/y in a real graphics API
int bytesPerRow = width / 8;
int rowBase = bytesPerRow * y;
int startOffset = x1 % 8;
int endOffset = x2 % 8;
int startByte = x1 / 8;
int endByte = x2 / 8;
// masks use int then cast; Java bytes are signed
int startMask = 0xFF >>> startOffset;
int endMask = 0xFF << (7 - endOffset);
endMask &= 0xFF;
if (startByte == endByte) {
// both ends inside one byte
int mask = startMask & endMask;
screen[rowBase + startByte] |= (byte) mask;
return;
}
// left partial (if any bits remain from startOffset to end of byte)
screen[rowBase + startByte] |= (byte) startMask;
// full middle bytes
for (int b = startByte + 1; b <= endByte - 1; b++) {
screen[rowBase + b] = (byte) 0xFF;
// or |= (byte) 0xFF if you prefer pure OR everywhere
}
// right partial
screen[rowBase + endByte] |= (byte) endMask;
}
चलाकर देखो, चौड़ाई 32 (४ बाइट/पंक्ति), रेखा x1 = 5, x2 = 26, y = 0:
| हिस्सा | बाइट स्तंभ | मास्क / मान | मतलब |
|---|---|---|---|
| शुरू | ० | 0xFF >>> 5 = 0x07 |
पिक्सेल ५,६,७ |
| पूरा | १ | 0xFF |
पिक्सेल ८-१५ |
| पूरा | २ | 0xFF |
पिक्सेल १६-२३ |
| अंत | ३ | 0xFF << (7-2) = 0xE0 |
पिक्सेल २४,२५,२६ (endOffset = 2) |
startByte = 0, endByte = 3। बीच का लूप b = 1 और b = 2 चलाता है। एक-बाइट वाला रास्ता नहीं चलता।
एक ही बाइट की जाँच
x1 = 10, x2 = 13, चौड़ाई 32: दोनों बाइट स्तंभ 1 में, ऑफसेट 2 और 5।
startMask = 0xFF >>> 2 = 00111111
endMask = 0xFF << (7-5) = 11111100 (low 8)
combined = 00111100
पिक्सेल १०,११,१२,१३ जलते हैं। पड़ोसी ८,९,१४,१५ अगर बुझे थे तो बुझे रहते हैं।
सीधा संदर्भ (टेस्ट के लिए)
void drawLineNaive(byte[] screen, int width, int x1, int x2, int y) {
if (x1 > x2) {
int t = x1;
x1 = x2;
x2 = t;
}
for (int x = x1; x <= x2; x++) {
int index = (width / 8) * y + (x / 8);
int bit = 7 - (x % 8);
screen[index] |= (byte) (1 << bit);
}
}
दोनों को यादृच्छिक रेंज पर मिलाओ। अगर अलग पड़ें तो मास्क वाला गलत है।
५. जटिलता तालिका
| तरीका | समय | अतिरिक्त जगह | नोट |
|---|---|---|---|
| हर पिक्सेल पर सेटबिट लूप | ओ(एल) | ओ(१) | एल = x२ - x१ + १ |
| पूरे बाइट + २ किनारे मास्क | ओ(बी) | ओ(१) | बी ≈ रेखा के बाइट स्तंभ, लगभग एल/८ |
| पूरी नई पंक्ति बनाना | ओ(चौड़ाई) | ओ(चौड़ाई/८) | एक रेखा के लिए ज़्यादा |
लंबी रेखाओं पर बी लगभग एल से आठ गुना छोटा। इसलिए इंटरव्यू में थोक भरना चाहते हैं। छोटी रेखाओं पर दोनों ठीक; मास्क वाला दिखाता है कि पैकिंग समझते हो।
६. किनारे के केस और आम गलतियाँ
इंटरव्यूअर ये छेदते हैं:
x1 == x2: एक पिक्सेल। एक-बाइट रास्ता, एक-बिट मास्क।- एक ही बाइट में कई पिक्सेल: मास्क का
ANDज़रूरी। भूलना क्लासिक बग। - बिल्कुल पूरे बाइट (
x1 % 8 == 0औरx2 % 8 == 7): शुरू/अंत मास्क0xFF। एक-बाइट बनाम बहु संरचना सही रहती है। - बीच में कोई पूरा बाइट नहीं: सिर्फ दो पड़ोसी आंशिक। लूप का शरीर नहीं चलता।
x1 > x2: पहले अदला-बदली या खाली परिभाषा। चुपचाप कुछ न खींचना बिना कहे मत।yरेंज से बाहर /xचौड़ाई से आगे: असली कोड जाँचे। स्केच में नोट करो।- जावा में साइन वाला
byte:(byte) 0xFFहै-1। बिट पैटर्न के लिए ठीक। मास्कintमें बनाओ, फिर कास्ट। - पहले से नकारात्मक मास्क पर
>>: धनात्मक0xFFसे शिफ्ट करो। - आंशिक पर
|=की जगह=: रेखा से बाहर के पिक्सेल मिट जाते हैं। - बाएँ एलएसबी मानना: एमएसबी-बाएँ बताओ (या मास्क पलटो)।
आम गलतियाँ:
१. एक-बाइट शाखा न होना। शुरू मास्क, फिर अंत, बीच में गलत 0xFF।
२. पूरे बाइट रेंज पर ऑफ-बाय-वन। 0xFF लूप में startByte या endByte शामिल कर आंशिक बिगाड़ना।
३. गलत अंत मास्क सूत्र। 0xFF << (7 - endOffset) और ८-बिट मास्क चुनो।
४. width / 8 स्ट्राइड भूलना। सूचकांक rowBase + byteCol है, सपाट x नहीं।
५. चौड़ाई को पहले से बाइट समझना। क्लासिक कथन में पिक्सेल हैं।
६. पूरी स्क्रीन साफ करना। ड्रॉ का मतलब रेखा के बिट जलाना, बफर को सिर्फ उसी रेखा से नहीं भरना।
छोटा धुआँ टेस्ट:
byte[] screen = new byte[4]; // width 16, height 2
drawLine(screen, 16, 3, 12, 0);
// row 0: expect roughly 00011111 11111000
System.out.printf("%8s %8s%n",
String.format("%8s", Integer.toBinaryString(screen[0] & 0xFF)).replace(' ', '0'),
String.format("%8s", Integer.toBinaryString(screen[1] & 0xFF)).replace(' ', '0'));
byte[] a = new byte[8];
byte[] b = new byte[8];
drawLine(a, 32, 5, 26, 0);
drawLineNaive(b, 32, 5, 26, 0);
// assert Arrays.equals(a, b)
७. दोस्त को समझाओ सार
ड्रॉ लाइन एकरंगी स्क्रीन को बाइट में पैक करती है, हर में आठ पिक्सेल। तुम एक क्षैतिज खंड रंगते हो।
१. (x, y) को बाइट सूचकांक दो: स्ट्राइड width / 8, बिट x % 8 से (बाएँ एमएसबी)।
२. सीधा: हर पिक्सेल पर एक-बिट मास्क OR। सही, समय रेखा-लंबाई के अनुपात।
३. बेहतर: पहले आंशिक पर मास्क, बीच के हर पूरे बाइट पर 0xFF, आखिरी आंशिक पर मास्क।
४. शुरू और अंत एक बाइट में हों तो दोनों मास्क का AND, एक बार लगाओ।
५. किनारों पर |= ताकि पड़ोसी न मिटें। जावा के साइन बाइट और पूरे-बाइट रेंज के ऑफ-बाय-वन संभालो।
अगर कागज़ पर १६ पिक्सेल चौड़ी पंक्ति खींच सको, x1 और x2 चिन्हित करो, दोनों मास्क द्विआधारी में लिखो, और बता सको एक ही बाइट क्यों खास है, तो समस्या ५.८ तुम्हारी है। अध्याय ५ एक ग्राफिक्स के टुकड़े पर बंद होता है जो असल में बिटसेट पर रेंज अपडेट है।
श्रृंखला
- गाइड: सीटीसीआई सीरीज़ गाइड
- पिछला: पेयरवाइज़ स्वैप
- अगला: द हेवी पिल