问题描述
假设我正在制作一个国际象棋应用程序,其中的位置存储如下:
Say I'm making a chess app, in which a position is stored like this:
struct Position {
var pieces: Set<Piece>
// some other stuff
}
Piece
的定义如下:
struct Piece: Hashable {
var row: Int
var column: Int
let player: Player
let type: PieceType
var hashValue: Int {
return 8 * row + column
}
}
Player
和PieceType
是简单的枚举:
enum Player {
case White, Black
}
enum PieceType {
case Queen, King, ...
}
现在,我想按其在板上的位置访问Position
中的Piece
. Piece
的哈希值由其位置唯一确定,因此应该可以在恒定时间内访问Piece
.但是,Swift集不具有通过其哈希值获取其元素之一的功能.我所能想到的就是
Now, I would like to access a Piece
in a Position
by its position on the board. The hash value of a Piece
is uniquely determined by its position, so access to a Piece
should be possible in constant time. However, a Swift set doesn't have a function to get one of its elements by its hash value. All I could come up with is
for piece in pieces {
if piece.hashValue == 25 {
// do something
}
}
...但是很明显,这是线性时间,而不是恒定时间.
...but obviously, this runs in linear time, not in constant time.
解决此问题的一种方法是不使用集合,而是使用数组:
A way to solve this problem is to not use a set, but an array instead:
var pieces: [Piece?]
然后我可以用pieces[25]
恒定时间访问特定位置的作品.我确实发现它不太优雅,因为此方法将每个Piece
的位置存储两次:通过pieces
数组中的位置以及通过row
和column
变量的值.
Then I can access the piece at a certain position simply with pieces[25]
, in constant time. I do find this less elegant, because this method stores the position of each Piece
twice: by the position in the pieces
array and by the values of the row
and column
variables.
是否有一种方法可以通过其散列值(恒定时间)访问set元素?还是应该只使用数组?
Is there a way to access a set element by its hash value (in constant time)? Or should I just use an array?
推荐答案
序言:
- 因为有64个正方形,所以最好是由可选件组成的阵列
- 通常,您使用带有Int键的字典作为稀疏数组(请参见下面的示例)
- 您不应仅将hashValue用于位置,因为它应考虑所有属性(在下面的示例中,我将位置更改为位置)-尽管在这种情况下,我知道除了短暂地没有2个块可以具有相同的位置,因此可能还可以
我该如何编码:
struct Piece {
var row: Int
var column: Int
let player: Player
let type: PieceType
var location: Int {
return 8 * row + column
}
}
struct Board {
var pieces = [Int : Piece]()
init(pieces: Piece...) {
pieces.forEach {
self.pieces[$0.location] = $0
}
}
}
let whiteKing = Piece(row: 0, column: 4, player: .White, type: .King)
let blackKing = Piece(row: 7, column: 3, player: .Black, type: .King)
let board = Board(pieces: whiteKing, blackKing)
board.pieces // [4: {row 0, column 4, White, King}, 59: {row 7, column 3, Black, King}]
这篇关于通过其哈希值访问Swift set元素的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!