मैं अंत में खराब हो गई और कुछ पैसे बाहर बमबारी की। एआईपी (अमेरिकन इंस्टीट्यूट ऑफ फिजिक्स) में जॉन स्किलिंग द्वारा सी "प्रोग्रामिंग द हिल्बर्ट वक्र" में स्रोत कोड के साथ एक अच्छा, लघु लेख है (एआईपी कॉन्फ। प्रो। 707, 381 (2004) से) के लिए कोड के साथ एक परिशिष्ट है दोनों दिशाओं में मैपिंग्स। यह किसी भी आयाम> 1 के लिए काम करता है, रिकर्सिव नहीं है, राज्य-संक्रमण लुकअप टेबल का उपयोग नहीं करता है जो बड़ी मात्रा में स्मृति को पकड़ता है, और ज्यादातर बिट ऑपरेशंस का उपयोग करता है। इस प्रकार यह काफी तेज़ है और इसकी अच्छी स्मृति पदचिह्न है।
आप लेख खरीद करने के लिए चुनते हैं, तो मैं स्रोत कोड में एक त्रुटि की खोज की। एक्स [मैं]^= एक्स [मैं के लिए (;; i> = 0 i-- i = n-1)
:
कोड (समारोह TransposetoAxes में पाया) की निम्न पंक्ति त्रुटि है -1];
सुधार से अधिक या बराबर (> =) को (>) से अधिक में बदलने के लिए है। इस सुधार के बिना, एक्स सरणी को नकारात्मक सूचकांक का उपयोग करके एक्सेस किया जाता है जब चर "i" शून्य हो जाता है, जिससे प्रोग्राम विफल हो जाता है।
मैं लेख पढ़ने (जो कोड सहित सात पृष्ठ लंबा है) पढ़ने की अनुशंसा करता है, क्योंकि यह बताता है कि एल्गोरिदम कैसे काम करता है, जो स्पष्ट से बहुत दूर है।
मैं अपने खुद के इस्तेमाल के लिए सी # में अपने कोड का अनुवाद किया। कोड निम्नानुसार है। स्किलिंग आपके द्वारा पारित वेक्टर को ओवरराइट करने के स्थान पर परिवर्तन करता है। मैंने इनपुट वेक्टर का क्लोन बनाने और एक नई प्रतिलिपि बनाने का विकल्प चुना है। इसके अलावा, मैंने विस्तार विधियों के रूप में विधियों को लागू किया।
स्किलिंग का कोड हिल्बर्ट इंडेक्स को एक सरणी के रूप में संग्रहीत एक ट्रांसपोजर के रूप में दर्शाता है। मुझे बिट्स को अंतःस्थापित करने और एक बिगइन्टर बनाने के लिए और अधिक सुविधाजनक लगता है (शब्दकोशों में अधिक उपयोगी, लूपों में फिर से भरना आसान है), लेकिन मैंने उस ऑपरेशन को अनुकूलित किया और जादू संख्याओं, बिट ऑपरेशंस और इसी तरह के विपरीत, और कोड लंबा है, इसलिए मैंने इसे छोड़ दिया है।
namespace HilbertExtensions
{
/// <summary>
/// Convert between Hilbert index and N-dimensional points.
///
/// The Hilbert index is expressed as an array of transposed bits.
///
/// Example: 5 bits for each of n=3 coordinates.
/// 15-bit Hilbert integer = A B C D E F G H I J K L M N O is stored
/// as its Transpose ^
/// X[0] = A D G J M X[2]| 7
/// X[1] = B E H K N <-------> | /X[1]
/// X[2] = C F I L O axes |/
/// high low 0------> X[0]
///
/// NOTE: This algorithm is derived from work done by John Skilling and published in "Programming the Hilbert curve".
/// (c) 2004 American Institute of Physics.
///
/// </summary>
public static class HilbertCurveTransform
{
/// <summary>
/// Convert the Hilbert index into an N-dimensional point expressed as a vector of uints.
///
/// Note: In Skilling's paper, this function is named TransposetoAxes.
/// </summary>
/// <param name="transposedIndex">The Hilbert index stored in transposed form.</param>
/// <param name="bits">Number of bits per coordinate.</param>
/// <returns>Coordinate vector.</returns>
public static uint[] HilbertAxes(this uint[] transposedIndex, int bits)
{
var X = (uint[])transposedIndex.Clone();
int n = X.Length; // n: Number of dimensions
uint N = 2U << (bits - 1), P, Q, t;
int i;
// Gray decode by H^(H/2)
t = X[n - 1] >> 1;
// Corrected error in Skilling's paper on the following line. The appendix had i >= 0 leading to negative array index.
for (i = n - 1; i > 0; i--)
X[i] ^= X[i - 1];
X[0] ^= t;
// Undo excess work
for (Q = 2; Q != N; Q <<= 1)
{
P = Q - 1;
for (i = n - 1; i >= 0; i--)
if ((X[i] & Q) != 0U)
X[0] ^= P; // invert
else
{
t = (X[0]^X[i]) & P;
X[0] ^= t;
X[i] ^= t;
}
} // exchange
return X;
}
/// <summary>
/// Given the axes (coordinates) of a point in N-Dimensional space, find the distance to that point along the Hilbert curve.
/// That distance will be transposed; broken into pieces and distributed into an array.
///
/// The number of dimensions is the length of the hilbertAxes array.
///
/// Note: In Skilling's paper, this function is called AxestoTranspose.
/// </summary>
/// <param name="hilbertAxes">Point in N-space.</param>
/// <param name="bits">Depth of the Hilbert curve. If bits is one, this is the top-level Hilbert curve.</param>
/// <returns>The Hilbert distance (or index) as a transposed Hilbert index.</returns>
public static uint[] HilbertIndexTransposed(this uint[] hilbertAxes, int bits)
{
var X = (uint[])hilbertAxes.Clone();
var n = hilbertAxes.Length; // n: Number of dimensions
uint M = 1U << (bits - 1), P, Q, t;
int i;
// Inverse undo
for (Q = M; Q > 1; Q >>= 1)
{
P = Q - 1;
for (i = 0; i < n; i++)
if ((X[i] & Q) != 0)
X[0] ^= P; // invert
else
{
t = (X[0]^X[i]) & P;
X[0] ^= t;
X[i] ^= t;
}
} // exchange
// Gray encode
for (i = 1; i < n; i++)
X[i] ^= X[i - 1];
t = 0;
for (Q = M; Q > 1; Q >>= 1)
if ((X[n - 1] & Q)!=0)
t ^= Q - 1;
for (i = 0; i < n; i++)
X[i] ^= t;
return X;
}
}
}
मैंने सी # में जिथब में काम कोड पोस्ट किया है।
https://github.com/paulchernoch/HilbertTransformation
मैंने ओलाप डेटा के बहु आयामी मैपिंग के लिए हिल्बर्ट वक्र का उपयोग किया है, मैंने पाया कि प्रदर्शन के संदर्भ में यह सरल एल्गोरिदम से बेहतर नहीं था। लेकिन मैं आपके से आयामों के छोटे सेटों के साथ परीक्षण कर रहा था। मुझे यकीन नहीं है कि आपका वास्तविक प्रश्न क्या है। – Tom
अच्छा, मेरा सवाल है: "मैं यह कैसे करता हूं?" –
मैंने सप्ताहों में एक ही प्रश्न के उत्तर की तलाश में बिताए हैं। इस विषय पर कागजात या तो अनजान, या पठनीय हैं लेकिन बिना किसी कोड के दिए गए हैं। जब मुझे कोड मिल जाता है, तो मैं इसका पालन नहीं कर सकता, या यह कहता है कि दृष्टिकोण दस आयामों से अधिक पैमाने पर नहीं होगा। फिर भी, विशेषज्ञों का कहना है कि आप जिस दृष्टिकोण का पीछा कर रहे हैं वह ध्वनि है, इसलिए हार मत मानो! –