V 语言 -- 数据结构.Map

V 语言 – 数据结构.Map

V语言现在还在开发阶段,所以还有很多不成熟的地方。比如其中的map,还只是一个原型。下面我做一个简单的分析。

结构体定义

module builtin

struct map {
	// cap int
	// keys []string
	// table byteptr
	// keys_table *string
	// table *Entry
	element_size int
	// collisions []Entry
pub:
	entries      []Entry
	is_sorted    bool
}

struct Entry {
pub:
	key string
	val voidptr
	// linked list for collisions
	// next *Entry
}

可以看到,map的结构十分简单,只包含三个成员

  • element_size: 元素大小
  • entries: 实体集合
  • is_sorted: 是否排序

其中的is_sorted这个属性比较有意思,说明在方法里面会排序,用到排序则很有可能与提高查找效率有关。

下面再来看方法。

方法

对于一个map来说,用的最多的无非是插入元素和获取元素。

插入元素

// 插入一个元素
fn (m mut map) _set(key string, val voidptr) {
	e := m.new_entry(key, val) 
	for i := 0; i < m.entries.len; i++ {
		entry := m.entries[i]
		if entry.key == key {
			// e := Entry2{key: key, val: val}
			m.entries[i] = e
			return
		}
	}
	m.entries << e// m.new_entry(key, val)
	m.is_sorted = false
}

插入元素的过程可以描述为:

  1. 创建一个元素
  2. 遍历查找键是否重复
  3. 如果重复,则赋值
  4. 如果没重复,则添加到末尾

不难看出,插入用到了遍历,其时间复杂度为O(n),是一种很低效的算法。在后续有很大的优化空间。

查找元素

// 获取元素
fn (m map) get(key string, out voidptr) bool {
	if m.is_sorted {
		// println('\n\nget "$key" sorted')
		m.bs(key, 0, m.entries.len, out)
		return true
	}
	for i := 0; i < m.entries.len; i++ {
		entry := m.entries[i]
		if entry.key == key {
			C.memcpy(out, entry.val, m.element_size)
			return true
		}
	}
	return false
}

// 二分查找
fn (m map) bs(query string, start, end int, out voidptr) {
	// println('bs "$query" $start -> $end')
	mid := start + ((end - start) / 2)
	if end - start == 0 {
		last := m.entries[end]
		C.memcpy(out, last.val, m.element_size)
		return
	}
	if end - start == 1 {
		first := m.entries[start]
		C.memcpy(out, first.val, m.element_size)
		return
	}
	if mid >= m.entries.len {
		return
	}
	mid_msg := m.entries[mid]
	// println('mid.key=$mid_msg.key')
	if query < mid_msg.key {
		m.bs(query, start, mid, out)
		return
	}
	m.bs(query, mid, end, out)
}

查找的流程可以描述为:

  • 判断是否已经排序
  • 如果未排序则遍历查找
  • 如果已排序则二分查找(排序方法需要显式调用)

查找过程用到了二分查找(O(lgn)),和遍历(O(n)),但是大部分时候,开发者不会对map显式排序,所以真正起作用的是遍历操作,也是十分低效。

改进及评价

  1. map模块显然很不成熟,其结构和算法有很大改进空间。
  2. 如果采用数组作为存储容器,则至少也可以达到查找: O(lgn) -> 排序O(lgn) + 二分查找 O(lgn), 插入O(lgn) -> 查重O(lgn) + 插入O(1)。否则数据量稍大会非常慢。
  3. 如果采用Hash实现,则可达到O(1) + O(1)的速度,不过这要看v语言的开发者如何取舍。
  4. v语言当前还无法用于生产环境,尝鲜可以,但正式环境还不可用。其语言特性很有吸引力,但现在的完成度还不高,到稳定可用估计还需要些时日。