В поисках более эффективного алгоритма сортировки в javascript ES6

Question

Дайте мне знать, если это не уместно, чтобы спросить здесь.

В настоящее время я создаю приложение реакции с картой, имеющей разные маркеры (до 1000), и у каждого из них есть своя специфика. Пользователь может установить различные фильтры, и приложение должно показать соответствующий. В настоящее время у меня есть алгоритм, который работает, но я уверен, что мы можем сделать его более эффективным и менее ресурсоемким.

Вот код, который я должен далеко:

покажет, что важно.

Для объяснения при рендеринге у меня есть карта, на которой я отображаю весь маркер, и под ним у меня есть список всех фильтров, где пользователь может щелкнуть по нему, чтобы применить этот фильтр.

Спасибо за ваш вклад!

class SomeComponent extends Component {
    state = {
        allMarkers: [
            {id: "1", filter: ['weekout', 'restaurant'], latlng: {latitude: 37.78825, longitude: -122.4224},title:'42'},
            {id: "2", filter: ['weekout'], latlng: {latitude: 37.78814, longitude: -122.4314},title:'Taverne du mont belon'},
            {id: "3", filter: ['restaurant', 'party'], latlng: {latitude: 37.78825, longitude: -122.1224},title:'Chez Lapin'},
            {id: "4", filter: ['party'], latlng: {latitude: 37.78825, longitude: -122.3324},title:'Pizza toto'},
            // up to 1000
        ],
        filteredMarkers: [
        ],
        filters: [
            {id: "1", selected: true, text: 'filter', filter: 'weekout'},
            {id: "2", selected: true, text: 'filter', filter:'pin'},
            {id: "3", selected: true, text: 'filter', filter: 'party'},
            {id: "4", selected: true, text: 'filter', filter: 'restaurant'},
            {id: "5", selected: false, text: 'filter', filter: 'beer'},
            {id: "6", selected: true, text: 'filter', filter:'love'},
            {id: "7", selected: false, text: 'filter', filter:'yum'},
          ],
    }

  filterMarkers() {
    let activefilters = this.state.filters.map((item) => item.selected && item.filter);
    let markers = this.state.allMarkers;

    let filteredmarkers = markers.map((item) => activefilters
    .some(r => item.filter.includes(r)) && item)
    .filter((item) => item)
    this.setState({...this.state, filteredMarkers: filteredmarkers})
  }

  selectedFilter(id) {
    let selectedfilters = this.state.filters
    selectedfilters.map((filter) => filter.id == id ? filter.selected = !filter.selected : null)
    this.setState({...this.state, filters: selectedfilters})
    this.filterMarkers();
  }

  render() {
      return(
        <View>
        <MapView >        
          {this.state.filteredMarkers.map((marker, idx) => (
            <Marker
              key={idx}
              identifier={marker.id}
              coordinate={marker.latlng}
            />
          ))}
        </MapView>
            <FlatList 
            data={this.state.filters}
            renderItem={({item, idx}) => 
            <TouchableOpacity onPress={() => this.selectedFilter(item.id)}>
            <View >
                <Image source={item.img} idx={idx}/>
            </View>
            </TouchableOpacity>          
            }
            />
        </View>

      ) 
  }
}

Answer 1

Всякий раз, когда вы пытаетесь провести какую-либо оптимизацию, вы обычно торгуете между скоростью и памятью.Но сначала давайте проанализируем ваш текущий метод:

// don't need to worry here as your filter set is small
let activefilters = this.state.filters.map((item) => item.selected && item.filter)

let markers = this.state.allMarkers
let filteredmarkers = markers
  // will run totalMarkers * activeFilters * filtersPerMarker
  .map((item) => 
    activefilters.some(r => item.filter.includes(r)) && item
  )
  // will run totalMarkers
  .filter((item) => item)

Итак, поскольку у вас есть всего несколько фильтров, если вы хотите увеличить количество маркеров, производительность должна возрастать более или менее линейно по сложности, и это нормально.Это означает, что такие вещи, как маски и т. Д., Приведут вас к небольшому приросту производительности.

Если вы действительно хотите оптимизировать это, вы будете стремиться к O (1), которого вы могли бы достичь с помощью кэширования.Чтобы сделать это, вы в основном реструктурируете свои данные таким образом, чтобы вы могли выполнить мгновенный поиск.Если ваши маркеры статичны, то это нормально, но если вы часто добавляете и удаляете маркеры (или меняете их соответствующие фильтры), вам потребуется стратегия для восстановления ваших данных.Вы можете сделать что-то вроде следующего:

// run this once, and update when markers are added/removed or marker filters change
const cache = {}
state.allMarkers.forEach(marker => {
  const id = marker.filter.join('-')
  if(!cache[id]){ cache[id] = [] }
  cache[id].push(marker)
})

Теперь, чтобы получить отфильтрованные результаты, вы просто ищите кэш с измененным идентификатором.

const filterId = this.state.filters
  .filter(item => item.selected)
  .map(item => item.filter)
  .join('-')

const filteredMarkers = cache[filterId] || []

Вероятно, лучшеспособы обработки идентификаторов, но, надеюсь, вы поймете идею.

---

Дело в том, что это зависит от того, как ваши пользователи взаимодействуют с данными, и сколько данных у вас есть.Опять же, 1000 достаточно мал, чтобы не заметить никакой разницы в выборе алгоритма, и выполнение чего-либо большего, чем простой фильтр, который вы используете, будет усложнять вещи без необходимости.Также более вероятно, что любые проблемы с производительностью возникнут из-за рендеринга больших наборов, а не их организации.

Другими словами, пишите самый простой и читаемый код и оптимизируйте его только в том случае, если у вас есть действительно веские причины(то есть вы оценили и выяснили фактическое узкое место, если оно вообще у вас есть).Потратьте больше времени на то, чтобы сделать ваше приложение прекрасным!