Finite-control-set model predictive control (FCSMPC) techniques have been widely applied for power electronics, and motor drive. Furthermore, the principles of FCS-MPC have been extended to phase-locked loop (PLL), which called finiteposition-set PLL (FPS-PLL), for sensorless control of permanentmagnet synchronous generators (PMSGs) in wind turbine applications (WTAs). However, 64 iterations are essential to find the optimal rotor position, i.e., high computational burden. In this article, two computationally efficient (CE) FPS-PLLs are proposed for encoderless control of PMSGs in WTAs. The first CE-FPS-PLL1 reduces the number of iterations to 36 with slightly better accuracy than the FPS-PLL, while the second (novel) CE-FPS-PLL2 calls for only 24 iterations to find the best rotor position with significantly better accuracy than the FPS-PLL. The performance of the proposed CE-FPS-PLLs has been experimentally investigated, and compared with that of the FPS-PLL, and classical PLL using a 14.5-kW PMSG. Furthermore, the robustness of the proposed CE-FPS-PLLs is investigated against variations of the PMSG parameters.