什么数据结构最适合嵌套值和数值计数？ [英] What data structure is best suited for nested values and count of values?

问题描述

我有传入的数据流具有以下值：

国家/地区，州/州/州/州/州/州/州/州（例如50,22,12）。

我需要设计一个系统，它将保留上述值及其子值的出现次数。如果存在超过最大值的数值，而不是存储实际值存储ETC。

出现的国家和数量

状态和出现次数

城市和发生次数

在定义的时间间隔要求是计算所有计数以及子类型计数。
例如所以这个系统的输出值将是。

国家A 435，州B 264，城市C 300

国家B 123，州B 825，城市C 321

国家A 153，州B 122，城市C 534

我的系统强制执行以下限制。

1.无法使用任何数据库系统存储和检索值。

2.为了速度和简单性，这需要在内存中（因此限制存储的最大值）

3.以特定间隔清除值。

4.这些值是嵌套的，我不能使用单独的表来分别跟踪3个字段。

我已经考虑过使用自定义数据结构来存储嵌套值和计数。
我可以通过其他方式实现以下设计。可以使用哪些数据结构？
是否有任何现有的例子做类似的事情？

注意：这不是一个家庭作业，我在开发自己的应用程序，我被困在设计优雅的解决方案。如果您认为这个问题对于StackOverflow来说太笼统或不适当，在关闭或投票之前，请留下应该使用哪个论坛提出这个问题的问题。任何积极的反馈赞赏。

伪代码：

  class Location { 
 // local storage 
 private val subLocationCounter = HashMap [Location，Long]; 
 
 //添加新位置的方法
 addLocation（Location loc）
 //方法获取当前的位置数
 getCounts（）
 //递归获取当前位置值的方法
 
} 
  

解决方案

这是您的递归数据结构：

  import scala.collection.mutable 
 
案例类状态（var count：Int = 0，cities：mutable.Map [String，Int] = mutable.Map（））
案例类国家（var count：Int = 0，states：mutable .Map [String，State] = mutable.Map（））
 
 val countries = mutable.Map [String，Country]（）
 
列表（
 A，B，C），
（A，B，D），
（B，B，C $ b）.foreach {
 case（countryName，stateName，cityName）=> 
 val country = countries.getOrElseUpdate（countryName，new Country）
 val state = country.states.getOrElseUpdate（stateName，new State）
 country.count + = 1 
状态。 count + = 1 
 state.cities（cityName）= state.cities.getOrElse（cityName，0）+ 1 
} 
 
国家（A）
国家（B）
  

结果：

  res1：Country = Country（2，Map（B  - > State（2，Map（D  - > 1，C  - > 1））））
 res2：Country = Country（1，Map（B  - > State（1，Map（C  - > 1））））
  

I have incoming stream of data which has following values.
Country, City, State

Along with maximum number of unique values to store (e.g. 50,22,12).
I need to design a system which will keep count of occurrences of above values and its sub-values. If there are more than maximum number of values then instead of storing actual value store ETC.

Country and count of occurrences
States and count of occurrences
Cities and count of occurrences

At defined time interval requirement is to calculate all counts along with subtype counts. e.g. So output values from this system will be.

Country A 435, States B 264, City C 300
Country B 123, States B 825, City C 321
Country A 153, States B 122, City C 534

My system enforces following restrictions.
1. Can't use any database system to store and retrieve values.
2. For speed and use of simplicity this needs to be in memory (hence limit on maximum values stored)
3. Values are cleared at particular interval.
4. These values are nested, I can't use separate tables to keep track of 3 fields separately.

I have thought about using custom data structure which stores nested values and its count. What other ways I can achieve following design. Which data structures can be used? Are there any existing examples which does similar things?

Note : This is not a homework assignment, I am developing my own application and I am stuck at designing elegant solution for this requirement. If you think this question is too general or inappropriate for StackOverflow, before closing or voting it down leave remark which forum should be used to ask this question. Any positive feedback appreciated.

Pseudo code:

class Location { 
// local storage
private val subLocationCounter = HashMap[Location, Long]; 

// method to add new location 
addLocation(Location loc) 
// method to get current count of locations
getCounts()
// method to get current count of locations values recursively 

} 

解决方案

Here is your "recursive data structure":

import scala.collection.mutable

case class State(var count:Int = 0, cities:mutable.Map[String, Int] = mutable.Map())
case class Country(var count:Int = 0, states:mutable.Map[String, State] = mutable.Map())

val countries = mutable.Map[String, Country]()

List(
  ("A", "B", "C"),
  ("A", "B", "D"),
  ("B", "B", "C")
).foreach {
  case (countryName, stateName, cityName) =>
    val country = countries.getOrElseUpdate(countryName, new Country)
    val state = country.states.getOrElseUpdate(stateName, new State)
    country.count += 1
    state.count += 1
    state.cities(cityName) = state.cities.getOrElse(cityName, 0) + 1
}

countries("A")
countries("B")

Results:

res1: Country = Country(2,Map(B -> State(2,Map(D -> 1, C -> 1))))
res2: Country = Country(1,Map(B -> State(1,Map(C -> 1))))

这篇关于什么数据结构最适合嵌套值和数值计数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！