NumPy: np.lexsort अस्पष्ट/सहिष्णु तुलना के साथ

Question

मेरे पास तीन आयामों में N अंक का संग्रह है। इन्हें (N,3) के आकार के साथ np.array के रूप में संग्रहीत किया जाता है। सभी बिंदु ~1e-5 होने के किसी भी दो बिंदुओं के बीच न्यूनतम दूरी के साथ अलग हैं। मैं उन आदेशों को फिर से शुरू करने के साधनों की तलाश में हूं, जो np.array में उनके वर्तमान क्रम से स्वतंत्र हैं और व्यक्तिगत घटकों के छोटे परेशानियों के लिए मजबूत हैं।

In [6]: my_array = np.array([[-0.5, 0, 2**0.5], [0.5, 0, 2**0.5 - 1e-15]]) 

In [7]: my_array[np.lexsort(my_array.T)] 
Out[7]: 
array([[ 0.5  , 0.  , 1.41421356], 
     [-0.5  , 0.  , 1.41421356]]) 

जहां हम देख सकते हैं कि इस मामले में आदेश देने की अत्यंत है:

पहली आवश्यकता को संतुष्ट करने का सबसे सरल साधन

np.lexsort(my_array.T) 

लेकिन इस मजबूती विभाग में विफल रहता है के साथ np.lexsort साथ है परेशानियों के प्रति संवेदनशील। इसलिए मैं np.lexsort का एक अस्पष्ट संस्करण ढूंढ रहा हूं जो अगले अक्ष पर आगे बढ़ेगा यदि एक अक्ष में दो मान epsilon की सहिष्णुता के भीतर हैं। (या कोई वैकल्पिक तंत्र जो मुझे ऑर्डर प्राप्त करने की अनुमति देगा।)

जैसा कि मेरे आवेदन में इन संग्रहों में से कई मिलियन हैं, जिनमें से सभी को ऑर्डर करने की आवश्यकता है, प्रदर्शन एक चिंता का विषय है (यही कारण है कि मैंने अंधेरे से प्रयास नहीं किया है मेरे स्वयं के सहिष्णु np.lexsort को पहले बिना देखे कि इसे करने का बेहतर तरीका है)।

Answer 1

मेरे अंतिम समाधान था:

def fuzzysort(arr, idx, dim=0, tol=1e-6): 
    # Extract our dimension and argsort 
    arrd = arr[dim] 
    srtdidx = sorted(idx, key=arrd.__getitem__) 

    i, ix = 0, srtdidx[0] 
    for j, jx in enumerate(srtdidx[1:], start=1): 
     if arrd[jx] - arrd[ix] >= tol: 
      if j - i > 1: 
       srtdidx[i:j] = fuzzysort(arr, srtdidx[i:j], dim + 1, tol) 
      i, ix = j, jx 

    if i != j: 
     srtdidx[i:] = fuzzysort(arr, srtdidx[i:], dim + 1, tol) 

    return srtdidx 

मैं ध्यान दें कि यह थोड़ा अधिक-इंजीनियर ऊपर वर्णित समस्या के लिए है। np.lexsort के साथ सरणी को ट्रांसपोज़ड फॉर्म में पारित किया जाना चाहिए। idx पैरामीटर एक को नियंत्रित करने के लिए अनुमति देता है कि सूचकांक क्या माना जाता है (तत्वों को क्रुद्ध रूप से मुखौटा करने की अनुमति देता है)। अन्यथा list(xrange(0, N)) करेगा।

प्रदर्शन अच्छा नहीं है। हालांकि, यह ज्यादातर बुरी तरह व्यवहार करने वाले नम्पी स्केलर प्रकारों का एक परिणाम है। सरणी पर tolist() को कॉल करने से कुछ हद तक स्थिति में सुधार होता है।

Answer 2

मैं एक ही समस्या में ठोकर खाई, केवल एक्स, वाई निर्देशांक की एक सूची के साथ 2 डी में, जिसे मुझे सहिष्णुता के साथ क्रमबद्ध करने की आवश्यकता थी।

def tolerance_sort(array, tolerance): 
    array_sorted = np.copy(array[np.lexsort((array[:, 0], array[:, 1]))]) 
    sort_range = [0] 
    for i in range(array.shape[0] - 1): 
     if array_sorted[i + 1, 1] - array_sorted[i, 1] <= tolerance: 
      sort_range.append(i + 1) 
      continue 
     else: 
      sub_arr = np.take(array_sorted, sort_range, axis=0) 
      sub_arr_ord = np.copy(
       sub_arr[np.lexsort((sub_arr[:, 1], sub_arr[:, 0]))]) 
      array_sorted[slice(sort_range[0], sort_range[-1] + 
           1)] = sub_arr_ord 
      sort_range = [i + 1] 
    return array_sorted 

जो इस सॉर्ट करता:

array([[ 11. , 4. ], 
     [ 1. , 0. ], 
     [ 7. , 10. ], 
     [ 2. , 9. ], 
     [ 9. , 9. ], 
     [ 5. , 4. ], 
     [ 1. , 2. ], 
     [ 1. , 0. ], 
     [ 0. , 0.1 ], 
     [ 2. , 0.06]]) 

इस में

(tolerance = 0.1): मैं इस समाधान numpy.lexsort के आधार पर लेखन समाप्त हो गया

array([[ 0. , 0.1 ], 
     [ 1. , 0. ], 
     [ 1. , 0. ], 
     [ 2. , 0.06], 
     [ 1. , 2. ], 
     [ 5. , 4. ], 
     [ 11. , 4. ], 
     [ 2. , 9. ], 
     [ 9. , 9. ], 
     [ 7. , 10. ]]) 

मैं सामान्यीकरण के लिए समय नहीं था, इसलिए यह केवल 2 डी में काम करता है और वर्तमान में आपके पास सॉर्टिंग के क्रम पर कोई नियंत्रण नहीं है (पहले दूसरे कॉलम द्वारा और फिर पहले तक)।